Основна школа „Коста Војиновић” у Подујеву основана је решењем СО Подујево, бр. 14-13 од 18. маја 1994. године и уписана у судски регистар код Окружног привредног суда у Приштини, решењем бр. ФИ 389/94. од 08. фебруара 1994. године, ради основног образовања и васпитања деце у осмогодишњем трајању на територији града.

Седиште школе је у Подујеву у улици Светосавска бб, а од школске 1999/2000 године у улици Топличка 14 у Куршумлији.

Прва основна школа у Подујеву је основана 22. новембра 1921. године и почела je са радом у приватној кући. Године 1931. сазидана је зграда основне школе у центру града и радила је са малим прекидима. У току Другог светског рата била је четвороразредна и радила је у разним просторијама.

После ослобођења почела је нормално да ради као Основна школа „Братство-Јединство” све до 1990. године када добија нови, т.ј. садашњи назив „Коста Војиновић”.

Од школске 1999/2000. године, одлуком Министарства просвете, школа је привремено променила седиште и измештена у Куршумлију.