В августе того же года он благодаря заступничеству епископа Вегапетяна сдает при Петербургском университете экзамен на звание преподавателя армянского языка и получает должность младшего учителя в Лазаревском институте восточных языков в Москве. Это свидетельствовало о его хороших знаниях в области истории армянской литературы и языка. Лазаревский институт восточных языков сыграл в целом прогрессивную роль в развитии армянской культуры. Он содействовал укреплению связей армянского и русского народов и их культур. Однако профессора и преподаватели института в большинстве своем придерживались консервативных социально-политических взглядов. Появление Налбандяна в институте, по словам его учеников, оказалось «лучом света в темном царстве». Здесь он сблизился с профессором восточной филологии, известным уже тогда прогрессивным общественным деятелем, буржуазным демократом, просветителем Степаносом Назарянцем. Убежденный сторонник демократизации армянской литературы и сближения литературного армянского языка с народным, С. Назарянц стал обличителем клерикалов-архаистов, этих врагов армянской культуры, чем привлек на свою сторону молодого Налбандяна. Налбандян стал критиковать староверов и крепостников с более радикальных позиций, чем Назарянц, и сразу вызвал неприязнь попечителей Института восточных языков, армянских князей Лазаревых, магистра богословия института реакционера М. Мсеряна и других защитников духа средневековья. Его продолжал преследовать и Аштаракский. Чтобы избавиться от преследований со стороны церкви, Налбандян в 1854 г. снял с себя духовный сан. В том же году по настоянию Аштаракского и его друга, наместника Кавказа князя Воронцова, он был арестован и заключен в одну из московских тюрем по обвинению в оскорблении главы армянской церкви. За недоказанностью предъявленного обвинения Налбандян вскоре был освобожден, однако он лишился должности учителя Лазаревского института. Это не обескуражило Налбандяна. Он попытался поступить на медицинский факультет Московского университета. Таких попыток Налбандян сделал несколько, но каждый раз его проваливали на экзаменах. Основную роль здесь сыграло определение «неблагонадежный», данное ему армянскими крепостниками. Налбандяну все же удалось определиться вольнослушателем медицинского факультета, и в течение четырех лет (1855–1858), несмотря на материальные трудности и интриги своих политических врагов, он упорно овладевает науками. Письма Налбандяна к родным и друзьям свидетельствуют о том, что в этот период он особенно увлекался естествознанием. Вместе с тем серьезное внимание он уделял изучению русской демократической общественной мысли, свободолюбивой литературы. В формировании его мировоззрения в московский период решающую роль стала играть передовая русская культура, такие ее великие представители, как A. С. Пушкин, М. Ю. Лермонтов, Н. В. Гоголь, B. Г. Белинский, А. И. Герцен, Н. Г. Чернышевский, а также знаменитый естествоиспытатель-эволюционист К. Рулье и другие русские ученые-материалисты. В своих письмах Налбандян с любовью говорит о Пушкине, Лермонтове, стихотворения которых он переводил на армянский язык, и Гоголе. Поэт Р. Патканян сообщает, что Налбандян в эти годы пристально следил за деятельностью Искандера (Герцена), зачитывался «Полярной звездой» и «Колоколом».
Не случайно Налбандян был одним из первых армянских мыслителей, осознавших единство интересов армянского и русского народов. В этом проявились как его историческая прозорливость и революционное чутье, так и воспринятый им дух русской революционно-демократической идеологии. Уже в период учебы в Московском университете Налбандян пришел к выводу, что национально-освободительное движение армянского народа должно развиваться в единстве с русским демократическим движением, и это в дальнейшем определило его идейно-политическую и организационную связь с русской революционной демократией.
В годы учебы в Московском университете Налбандян пишет стихи, полные призыва к мужественной борьбе с существующими порядками, с тиранией, изобличает армянских попов и русских крепостников. Он становится кумиром прогрессивного армянского студенчества Москвы, активно участвует в деятельности различных кружков и, вероятно, вступает в тайную революционную организацию Московского университета «Библиотека казанских студентов». Во всяком случае, он был лично знаком с некоторыми из руководителей этой организации.