Il Comitato è stato istituito dall'articolo 18, comma 1, della legge 30 settembre 1993, n. 388, che ha ratificato l'Accordo di Schengen, relativo all'eliminazione graduale dei controlli alle frontiere comuni, nonché la Convenzione di applicazione dell'Accordo medesimo. La legge di ratifica ha infatti previsto, accanto alle disposizioni immediatamente attuative dei due trattati, l'istituzione di un Comitato parlamentare incaricato di "esaminare l'attuazione ed il funzionamento della Convenzione di applicazione dell'Accordo di Schengen", attraverso l'espressione di un parere vincolante sui progetti di decisione, vincolanti per l'Italia, pendenti dinanzi al Comitato esecutivo contemplato dal titolo VII della citata Convenzione.

Successivamente all'entrata in vigore del Trattato di Amsterdam (1° maggio 1999), il Consiglio dell'Unione europea è divenuto competente per l'adozione di misure volte ad assicurare la libera circolazione delle persone. La cooperazione Schengen è stata pertanto incorporata nell'ambito dell'Unione europea, e con essa tutto il complesso di norme rientrante nel c.d. acquis di Schengen. A partire da tale data la materia ha cessato di essere oggetto di cooperazione intergovernativa, rientrando a pieno titolo nel quadro giuridico dell'Unione europea.

Il Comitato è composto da dieci deputati e dieci senatori, nominati dai Presidenti delle Camere, in modo da rispecchiare la proporzione dei gruppi parlamentari. Il Comitato elegge al suo interno, così come stabilisce la legge istitutiva all'articolo 18, comma 3, un Presidente ed un Vicepresidente. Si è ritenuto tuttavia, con l'assenso dei Presidenti delle Camere, di integrare la composizione dell'Ufficio di Presidenza con l'elezione di un segretario.

La legge 23 marzo 1998, n. 93, con la quale è stata ratificata ed eseguita la Convenzione Europol, istitutiva dell'Ufficio europeo di polizia, ha inoltre attribuito al Comitato funzioni di vigilanza sull'Unità nazionale Europol. L'Ufficio europeo di polizia persegue il miglioramento della cooperazione di polizia tra gli Stati membri. Secondo quanto disposto dalla Convenzione, ogni Stato membro costituisce o designa un'unità nazionale, unico organo di collegamento fra Europol e i servizi nazionali competenti. La legge n. 93 del 1998 ha altresì previsto che il Governo trasmetta annualmente al Comitato una relazione sull'attuazione della Convenzione Europol.

L'articolo 37 della legge 30 luglio 2002, n. 189, in materia di immigrazione e di asilo, ha infine attribuito al Comitato compiti di indirizzo e vigilanza circa la concreta attuazione della legge, nonché degli accordi internazionali e della restante legislazione in materia di immigrazione ed asilo, prevedendone la seguente nuova denominazione: "Comitato parlamentare di controllo sull'attuazione dell'accordo di Schengen, di vigilanza sull'attività di Europol, di controllo e vigilanza in materia di immigrazione". In particolare, per effetto del citato articolo 37, le funzioni di vigilanza e controllo del Comitato si estendono alla concreta attuazione della normativa sull'immigrazione e l'asilo, nonché degli accordi internazionali in materia. Si prevede, inoltre, che il Governo presenti annualmente una relazione al Comitato e che lo stesso riferisca annualmente alle Camere sulla propria attività.

La legge 30 giugno 2009, n. 85 che sancisce l'adesione della Repubblica italiana al Trattato di Prum, (istitutivo di una banca dati nazionale del DNA) stabilisce inoltre, all'art.30, che il Ministro dell'interno informi annualmente il Comitato parlamentare sullo stato di attuazione delle previsioni del Trattato, sulle azioni intraprese e sugli accordi conclusi, con specifico riferimento a quelli attuativi di cui all'articolo 44 del Trattato medesimo.