В 1939 году в г. Тара Омской области была открыта семилетняя школа № 4. Школа-семилетка - тип общеобразовательной школы в составе 7 классов, дававшая учащимся неполное среднее образование. 10 августа 1930г. Постановлением ВЦИК и СНК РСФСР был принят закон «О введении всеобщего обязательного начального обучения». Согласно закону все дети должны были обучаться в начальной школе, а переростки, так называли детей, не получивших начального образования, позже - семилетнего образования, которое стало обязательным, также должны были сесть за парты. Так решался вопрос о ликвидации повсеместной не грамотности, как среди школьников, так и среди более взрослого населения. Находилась школа переростков, как называли её в народе, по адресу: г. Тара, ул. Луначарского, д.51. В годы Великой Отечественной войны в здании школы была размещена эвакуированная 2-ая Ленинградская военно-морская специальная школа, которая готовила юношей к службе на флоте. Связь с бывшими воспитанниками мореходки поддерживается на протяжении всех лет существования школы. На базе МОУ «Тарская СОШ №4» был создан музей 2-ой Ленинградской военно-морской специальной школы .
По воспоминаниям жителей города, из документов по личному составу известно, что в 1956-1957 учебном году школой руководил Бородин Н.А (имя, отчество в документах не уточняется). В истории школы оставили свой след такие руководители, как: директор Алгазин Николай Дементьевич (1958-1977гг.), директор Вайсман Я.И., директор Курашев А.В., директор Отмахова Анна Яковлевна (1977-1980гг), директор Сабаева Ливия Андреевна (1980-1981гг), директор Соловьёва Лариса Евгеньевна (1981-1991гг.), Павел Юрьевич Исаев (1991-1996гг.), Авласович Михаил Александрович (1997-2012гг.).
С 1992 года школа работает в новом типовом здании.
В 2001 году школа становится победителем в областном конкурсе воспитательных систем. В 2002 году, участвуя в первом областном фестивале инновационных проектов, творческая группа учителей заняла III место с проектом нравственно-патриотического воспитания «Школа – наш дом».
В 2002 году Указом Губернатора Омской области Л.К. Полежаева школе было присвоено имя Героя Советского Союза адмирала флота Советского Союза Н.Г. Кузнецова.
В июле 2005 года на территории школы был установлен бюст Герою Советского Союза адмиралу флота Н.Г. Кузнецова.
С 2010 года коллектив школы ведёт работу над реализацией программы развития школы «Сохранение и развитие одарённости детей». Цель программы: выявление, поддержка и создание условий для развития художественной, музыкальной, интеллектуальной, социальной, спортивной одарённости учащихся.
По результатам деятельности образовательных учреждений за 2022-2023 учебный год школа получила статус «Лучшее образовательное учреждение 2023 года».