30-åringen stoppade 26 av 27 skott och lade grunden till att Vegas kunde ta sin första tvåpoängare sedan NHL-premiären mot Seattle Kraken den 13 oktober.
Lehner tog samtliga skott i den första perioden, där Vegas gick ifrån till 2-0.
Han släppte sedan förbi sig kanadensiske Cale Makars reducering i slutet av den andra perioden, men roligare blev det inte för hemmalaget Colorado.
Det var Vegas andra seger för säsongen.
Laget ligger på elfte plats i den västra konferensen, en placering före Colorado efter sex spelade matcher.
MER NHL: Olofsson gjorde två mål på mästarlaget (26 okt)
NHL
Colorado Avalanche
1 - 3
Vegas Golden Knights
0-2, 1-0, 0-1
Ball Arena, Denver, CO
17724
| # | Lag | S | V | F | VÖ | FÖ | GM-IM | M | P |
|---|---|---|---|---|---|---|---|---|---|
| 1 |  COLColorado Avalanche | 82 | 46 | 19 | 10 | 7 | 312-234 | +78 | 119 |
| 2 |  MINMinnesota Wild | 82 | 37 | 22 | 16 | 7 | 310-253 | +57 | 113 |
| 3 |  CGYCalgary Flames | 82 | 44 | 21 | 6 | 11 | 293-208 | +85 | 111 |
| 4 |  STLSt. Louis Blues | 82 | 43 | 22 | 6 | 11 | 311-242 | +69 | 109 |
| 5 |  EDMEdmonton Oilers | 82 | 38 | 27 | 11 | 6 | 290-252 | +38 | 104 |
| 6 |  LAKLos Angeles Kings | 82 | 35 | 27 | 9 | 11 | 239-236 | +3 | 99 |
| 7 |  DALDallas Stars | 82 | 31 | 30 | 15 | 6 | 238-246 | -8 | 98 |
| 8 |  NSHNashville Predators | 82 | 35 | 30 | 10 | 7 | 266-252 | +14 | 97 |
| 9 |  VGKVegas Golden Knights | 82 | 34 | 31 | 9 | 8 | 266-248 | +18 | 94 |
| 10 |  VANVancouver Canucks | 82 | 32 | 30 | 8 | 12 | 249-236 | +13 | 92 |
| 11 |  WPGWinnipeg Jets | 82 | 32 | 32 | 7 | 11 | 252-257 | -5 | 89 |
| 12 |  SJSSan Jose Sharks | 82 | 22 | 37 | 10 | 13 | 214-264 | -50 | 77 |
| 13 |  ANAAnaheim Ducks | 82 | 22 | 37 | 9 | 14 | 232-271 | -39 | 76 |
| 14 |  CHIChicago Blackhawks | 82 | 16 | 42 | 12 | 12 | 219-291 | -72 | 68 |
| 15 |  SEASeattle Kraken | 82 | 23 | 49 | 4 | 6 | 216-285 | -69 | 60 |
| 16 |  ARIArizona Coyotes | 82 | 18 | 50 | 7 | 7 | 207-313 | -106 | 57 |