Из корпусных впечатлений в памяти Потебни и его товарищей должно было сохраниться такое событие, как открытие памятника в честь битв за Полоцк на плацу перед зданием корпуса. Торжество происходило 26 августа 1850 года. Дата была выбрана не случайно: она совпадала с годовщинами славных побед русского оружия в 1612 и 1812 годах. В один ряд с этими победами устроители торжества поставили взятие Варшавы в 1831 году, завершившее жестокое подавление польского восстания. Эта бестактность оскорбляла национальные чувства многих воспитанников.
В конце июля 1854 года Потебня вместе со многими своими сверстниками из шестнадцатого выпуска Полоцкого кадетского корпуса был зачислен для завершения военного образования в Дворянский полк (Константиновское военное училище). Новые впечатления и встречи, быстрое расширение кругозора, обострение интереса к общественному движению — вот что означал для Потебни переезд в Петербург. Одновременно с ним в Дворянском полку находился будущий активный деятель офицерской организации Петр Краснопевцев. Годом раньше Потебни учились Ярослав Домбровский и Павел Огородников, годом позже — Зыгмунт Падлевский и Константин Жебровский.
С окончанием Крымской войны и смертью Николая I резко изменилась политическая атмосфера. Наступила эпоха падения крепостного права. Освободительные идеи захватили армейскую молодежь. Они легко воспринимались молодыми офицерами, выходцами из бедных дворянских семей, по образу жизни сливавшимися с разночинской средой. Таким был и Потебня, о котором знавшие его люди говорили: «простой человек, простой по положению, чину и воспитанию».
16 июня 1856 года восемнадцатилетний Потебня был выпущен прапорщиком в Шлиссельбургский пехотный полк 4-й пехотной дивизии, стоявшей в Царстве Польском. Через два года он, однако, вновь оказался в Петербурге. На этот раз он был слушателем Царскосельской офицерской стрелковой школы. Здесь он учился с ноября 1858 по ноябрь 1859 года.
Пребывание в Петербурге оставило в Потебне не-язгладимый след. Он жадно читал передовые русские журналы — «Современник» со статьями Чернышевского и Добролюбова, новый остроумный сатирический журнал «Искру», издававшийся с 1859 года, новый военный журнал «Военный сборник», появившийся в 1858 году. В этом году в редакции его работал Чернышевский, и журнал энергично боролся против крепостнических порядков в армии и защищал человеческие права солдат. В руки Потебни попадали и широко распространявшиеся в России запретные листы «Колокола» и другие издания лондонской Вольной русской типографии. «Все, что знал, вычитал большей частью из русских журналов», — писал о нем Бакунин.
Живя в Царском Селе, Потебня наверняка слышал об офицерском кружке генштабистов, встречался с его участниками, а возможно, бывал и на их собраниях. Знакомые Потебни были в кружке военных инженеров, среди чернышевцев и в других офицерских кружках.
Под влиянием дискуссий в этих кружках и чтения в этот период сложились основные убеждения молодого офицера, созрело решение примкнуть к революционному лагерю. В этот период выработались и те личные качества Потебни, на которые обращали внимание все знавшие его люди. Потебня производил впечатление человека с головы до ног серьезного, преданного революции, чуждого всякой рисовки и тщеславия.
Есть основания предполагать, что в Царскосельской стрелковой школе также существовал офицерский кружок. Большая часть его участников сменялась ежегодно вместе с выпуском слушателей. Преемственность удавалось поддерживать через офицеров из постоянного состава школы и путем контактов между слушателями в осенние месяцы, когда почти одновременно проходили вступительные и выпускные экзамены. Участниками кружка в Царскосельской школе являлись, по-видимому, один из будущих руководителей «казанского заговора» Наполеон Иваницкий, члены революционной организации русских офицеров в Польше и петербургских военных кружков А. Н. Ган, С. Ю. Готский-Данилович, Н. А. Арен-даренко, М. В. Кюхельбекер, Д. 3. Якубовский и др. Внешние связи царскосельского кружка осуществлялись, вероятно, через Н. Н. Обручева, который был председателем учебного совета школы (он, между прочим, подписал выпускное удостоверение Потебни).