Родилась в Москве в семье переехавших в столицу в начале прошлого века уроженцев Баку — обрусевшего немца Александра Александровича Канненберга, личного юрисконсульта российского нефтепромышленника С. Г. Лианозова, и воспитаницы пансиона благородных девиц им. Св. Нины Александры Андреевны Ракитиной.
В годы Большого террора потеряла любимого старшего брата Анатолия .
В начале войны, рискуя жизнью, спасла отца от неминуемой высылки, которой подверглись все этнические немцы. Спрятав его, она предложила явившемуся с ордером наряду НКВД, что сама отправится в ссылку вместо отца. Неожиданно закончилось это, продолжавшееся более суток неравное противостояние, на протяжении которого наряд дежурил в засаде на квартире на Спиридоновке, 16, а рядом с Ниной Велеховой, тогда еще Канненберг, отказывавшейся выдать местонахождение отца, неотлучно был её однокурсник Юлий Шуб (сам — сын расстрелянного), с которым они только что расписались. Победили слабые: конвой, махнув рукой, ушел.Любовь к театру возникла в детстве: мама Н. А. Велеховой работала машинисткой в знаменитом тогда Госцентюзе (впоследствии МТЮЗе), романтические спектакли и звезды этого театра — Лев Потемкин, Георгий Дебрие, Валентин Колесаев, Марина Зорина, Нина Сытина и другие — навсегда остались среди самых ярких театральных впечатлений будущего критика. После Госцентюза, в годы юности любимым театром стал Вахтанговский с его яркой, праздничной формой, с его великолепными актерами, в частности, самым красивым театральным дуэтом страны, Дмитрием Дорлиаком и Валентиной Вагриной, блиставшими в инсценировке «Человеческой комедии» Бальзака.