Училиштето започна со работа во 1922 година со една училница, сместена во стара зграда зад денешно кино Маџари, како српско училиште, во 1932 година со доброволна работа на месното население е изградено основно училиште до 4 одделение. Од 1941 година до 1944 година во Маџари имало бугарско училиште кое го носело името ,,Кирил и Методиј“.

По ослободувањето на нашата земја, во ноември 1944 година, во селото Маџари се отвара училиште на македонски јазик ,,Кирил и Методиј“ кое го задржува името до 1961 година. Истата година на влезот на градот, од левата страна на автопатот се гради нова училишна зграда  и училиштето го добива името „Наум Наумовски-Борче“ по името на народниот херој и народен пратеник  за Маџари. Училиштето започна со работа на 01.02 1961 година.

Тогашното мало место се измени по катастрофалниот земјотрес во 1963 година, па селото Маџари се прошири со населбата Маџари 2, со изградени бараки и станбени згради. Со тоа се зголеми бројот на ученици и се појави потреба за доградба на училишната зграда. Во март 1977 година се отвараат две групи забавиште, а есента истата година започнува со работа дневниот престој со две групи во кои се опфатени ученици од прво до четврто одделение.

Во 1979 година, од силни дождови и излевање на реката Вардар, месноста беше  поплавена и училиштето згрижи 1100 лица кои настрадаа во оваа елементарна непогода. Тоа придонесе училиштето на неколку пати да биде реновирано. Оттогаш континуирано се прават напори да се подобрат условите за учење.

Поддршката и соработката со локалната самоуправа е клучот за големи придобивки и брз развој на нашето училиште во последните години.   Добрата соработка допринесе да се реализираат проекти кои  имаат позитивен ефект на воспитно-образовната работа во училиштето. Така под покровителство на Агенцијата за млади и спорт, Советот на општина Гази Баба и Владата на Република Македонија во дворот на училиштето се изгради спортската сала „Методија Андонов-Ченто“ и повеќенаменско спортско игралиште „Наум Наумовски-Борче“.

Училиштето својата воспитно-образовна работа ја организира и  реализира во просторни и материјални услови кои ги задоволуваат потребите за одржување на редовна настава и воннаставни активности. Во моментот располага со 22 училници, библиотека, медијатека, фискултурна сала, спортска сала  и повеќенаменско игралиште.