Faits : A. Par ordonnance pénale du 19 novembre 2014, A._, ressortissant guinéen, a été condamné à une peine pécuniaire de 45 jours-amende à 30 fr. le jour, sous déduction d'un jour de détention avant jugement, pour l'infraction de séjour illégal au sens de l'art. 115 al. 1 let. b de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20). A cette occasion, le sursis accordé par ordonnance pénale du 1 er octobre 2014 à la peine pécuniaire de 30 jours-amende à 30 fr. le jour pour séjour illégal a été révoqué. Le 21 novembre 2014, A._ a formé opposition contre l'ordonnance pénale susmentionnée. Il a également requis l'assistance judiciaire, requête rejetée le 4 décembre suivant par le Ministère public. Celui-ci a considéré que la cause ne présentait pas de difficultés particulières de fait ou de droit et était de peu de gravité. Le recours formé par l'intéressé contre cette décision a été rejeté par arrêt du 3 mars 2015 de la Chambre pénale de recours de la Cour de justice de la République et canton de Genève. En substance, cette juridiction a considéré que la sanction ne dépasserait pas le maximum de 120 jours-amende caractérisant les "cas bagatelles". B. Par mémoire du 20 avril 2015, A._ forme un recours en matière pénale contre ce jugement, concluant à son annulation. Il requiert l'octroi de l'assistance judiciaire et la nomination de son conseil en tant qu'avocat d'office. A titre subsidiaire, il demande le renvoi de la cause à l'autorité précédente afin qu'elle lui accorde l'assistance judiciaire. Il sollicite également celle-ci pour la procédure fédérale. Invitée à se déterminer, l'autorité précédente s'est référée à ses considérants sans formuler d'observations. Quant au Ministère public, il a conclu au rejet du recours sans autres observations.