Nel 1987 entra nella lista del Pci nella circoscrizione Bari-Foggia. In quella campagna elettorale fu la candidata più giovane di tutto il sud Italia, raccogliendo 6.000 voti di preferenza. Negli anni successivi l'impegno politico la vede protagonista del Consorzio per l'istituzione dell'Università di Foggia, dove per dieci anni ha lavorato per la nascita dell'ateneo dauno. Sempre nei primi anni '90 è nominata membro del consiglio d'amministrazione dell'Ipab Maria Cristina di Savoia a Foggia. Nei primi anni di militanza nel Pci di Capitanata il lavoro politico si concentra soprattutto nella difesa dei residenti dei quartieri periferici di Foggia, che allora vivevano in condizioni di disagio e di degrado disumane. Nel 1986 diventa segretaria della sezione Imperiale del PCI.
Nel 1990 entra nella segreteria cittadina di Foggia del PCI.
Nel 1993 diventa componente della segreteria provinciale del PDS.
Nel 2002 entra nella segreteria regionale della Puglia dei Democratici di Sinistra.
Nel 1995 è candidata al Comune di Foggia. Eletta in consiglio comunale, inizia un'intensa attività amministrativa di controllo e di opposizione nei confronti dell'amministrazione di centrodestra che la porterà a ricoprire il ruolo di capogruppo del partito maggiore dell'opposizione nella consiliatura 1999-2004. Durante questo mandato, intensa è stata l'azione politica di contrasto e di proposizione, con particolare riferimento ai temi della qualità urbana e dell'assetto del territorio. Nel 2004 torna in consiglio comunale a Foggia. Incarico che ha lasciato il 1° gennaio del 2006 per assumere la presidenza dell'azienda speciale AMICA.

Il 2006 è un anno importante per Colomba Mongiello che, nelle elezioni politiche del 9 e 10 aprile, viene eletta al Senato della Repubblica, dove entra a far parte del gruppo parlamentare de l'Ulivo.

Intensissima è la sua partecipazione ai lavori parlamentari e a quelli delle commissioni di cui è componente. È infatti membro della 11a Commissione Permanente (lavoro, Previdenza sociale), della 13a Commissione permanente (Territorio, ambiente, beni ambientali), della Commissione parlamentare di inchiesta sul fenomeno degli infortuni sul lavoro (morti bianche), membro sostituto del Comitato parlamentare per i procedimenti di accusa, membro della Commissione Parlamentare per l'infanzia e membro della Commissione parlamentare per il controllo sull'attività degli enti gestori di forme obbligatorie di previdenza e assistenza sociale. In Senato la senatrice Mongiello è stata relatrice - sia all'assemblea che in Commissione - di importanti disegni di legge: fra di essi si ricorda, per la grande valenza in ambito economico e sociale - il ddl che reca disposizioni in materia di modalità per la risoluzione del contratto di lavoro per dimissioni volontarie del prestatore d'opera. La nuova norma combatte una pratica, particolarmente diffusa nel Mezzogiorno e che colpisce in modo rilevante le donne lavoratrici, con la quale alcuni datori di lavoro fanno sottoscrivere fin dal momento dell´assunzione le dimissioni dal posto occupato.

Nel campo dell'iniziativa legislativa ha presentato come prima firmataria due ddl, il 1093 e il 1594, riguardanti rispettivamente l'albo professionale dei centralinisti telefonici e degli operatori della comunicazione minorati della vista, e l'istituzione a Foggia di una sezione della Corte d'Appello di Bari, di una sezione della Corte d'appello di Bari in funzione di Corte d'assise d'appello e del tribunale per i minorenni.

Il 2007 l'ha vista protagonista del processo costituente del Partito democratico. Dalle primarie del 14 ottobre 2007 è risultata eletta, nella circoscrizione Foggia-Lucera, all'Assemblea Costituente Nazionale. Nell'assemblea è componente della Commissione che elaborato il Manifesto dei Valori del Partito Democratico.

Rieletta a Palazzo Madama alle elezioni legislative del 13 e 14 aprile 2008, Colomba Mongiello il 6 maggio 2008 è stata eletta segretario del Consiglio di Presidenza del Senato della Repubblica.