Faits: A. Le 25 septembre 2012, A._ a été arrêté dans le cadre d'une instruction conduite par le Ministère public du canton de Genève (ci-après: le Ministère public) et portant sur un trafic de stupéfiants. Il lui est reproché en substance de faire partie d'une équipe de trafiquants agissant en qualité de fournisseurs ou de grossistes pour approvisionner en héroïne le marché de détail à Genève. Il faisait en outre l'objet d'une interdiction d'entrée en Suisse valable jusqu'au 9 décembre 2013. Par ordonnance du 26 septembre 2012, le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc) a ordonné la détention provisoire du prénommé jusqu'au 26 novembre 2012, au motif qu'il existait des charges suffisantes ainsi que des risques de fuite et de collusion. Statuant sur recours de l'intéressé, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a confirmé cette décision par arrêt du 12 octobre 2012. Elle a retenu que les charges étaient suffisantes, que les risques précités étaient évidents et qu'aucune mesure de substitution n'était envisageable. B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt et d'ordonner sa mise en liberté immédiate, subsidiairement de renvoyer la cause à l'instance précédente pour nouvelle décision. Il requiert en outre l'octroi de l'assistance judiciaire. La Cour de justice a renoncé à se déterminer. Le Ministère public conclut au rejet du recours, en se référant aux considérants de l'arrêt attaqué. Le recourant a renoncé à formuler des observations complémentaires.