A partire dalla prima metà del secolo XVIII, i bandeirantes iniziano l'esplorazione delle miniere d'oro e di smeraldi de ouro e esmeralda e comincia a popolarsi l'interiore di Goiás; da allora questa regione comincia ad essere frequentata in quanto punto di passaggio della strada reale, usata per il commercio di oro e per l'affitto dei decimi territoriali della corona.
I documenti esistenti non indicano la data esatta della fondazione di Planaltina, perciò si considera convenzionalmente come data il 19 agosto 1859, ma esistono cronache di alcuni storici secondo le quali la città abbia più di 200 anni.
Secondo la tradizione orale, il primo nome del villaggio fu Mestre d'Armas, dovuto al fatto che nella regione si fosse stabilito un fabbro, esperto nell'arte di aggiustare e maneggiarmi armi, il quale ricevette il titolo di Mastro ("Mestre"), espressione che passò ad identificare tutto l'abitato.
Si attribuisce la fondazione del nucleo abitato dal quale sorse Planaltina a José Gomes Rabelo, fazendeiro che si trasferì dall'allora Capitale della Provincia di Goiás a Lagoa Bonita, estendendo in un secondo momento i suoi possedimenti fino alla dimora del "Mastro d'Armi". Costruirono una Capella de Taipa, come ex-voto fatto a San Sebastiano, perché li liberasse da un'epidemia che si era diffusa all'epoca. Dona Marta Carlos Alarcão, inoltre, si fece mandare dal Portogallo un'immagine del Santo, lavorata nel legno, perché fosse collocata nella cappella; questa fu poi sostituita da un'immagine più grande quando si ampliò l'intera costruzione. L'attuale chiesa di San Sebastiano conserva tuttora le stesse caratteristiche della sua creazione.
Il territorio dove si trovava "Mestre D'armas" appartenne, all'inizio a Vila di Santa Luzia (oggi Luziânia), essendosi trasferito a Julgado de Couros (oggi Formosa) il 20 giugno 1837. Ci furono successivi annessioni e cedimenti territoriali, provocate da sollevamenti popolari, per cui l'abitato appartenne alternativamente al territorio di Vila de Santa Luzia e a quello di Vila de Formosa.
Il 19 agosto 1859 secondo la Legge n°03 dell'Assemblea Provinciale di Goiás, fu creato il Distretto di Mestre D'armas, che secondo i termini della legge apparteneva al municipio di Formosa. Questa passò ad essere la data ufficiale della fondazione di Planaltina, secondo l'articolo 2 del Decreto N n°571 del 19 gennaio 1967.
Il 14 giugno 1917, secondo la legge nº 451, la città viene rinominata Planaltina.
Successivamente, in città fu posto un ufficio delle imposte per la riscossione delle imposte statali e federali. Nel 1892, l'arrivo della Commissione Cruls che realizzò i primi studi sulla fondazione della futura capitale federale nel Planalto Centrale, lega la storia di Planaltina a quella di Brasilia. L'allora Presidente della Repubblica Epitácio Pessoa emise il decreto nº 4494 del 18 gennaio 1922, decidendo la posa della prima pietra della futura capitale brasiliana. La posa avvenne il 7 settembre 1922.
Planaltina oggi conta circa 189 412 abitanti.
Divisione
A partire dal 21 aprile 1960, data dell'inaugurazione di Brasilia come capitale brasiliana, Planaltina vide il suo territorio diviso in due parti. L'antica sede del municipio goiano era localizzata nella parte che fu inclusa nel Distretto Federale e nella sua struttura amministrativa, come parte della regione amministrativa del Distretto Federale. L'altra parte, invece, che rimase esclusa dal quadrilatero del Distretto Federale, continuò a far parte dello stato di Goiás e la sua nuova sede ricevette il nome di Planaltina de Goiás, popolarmente conosciuta come Brasilinha ('Piccola Brasilia').