À l'époque de l'Ouest sauvage, même si dans Red Dead Redemption la fin de cette période se rapproche, de nombreuses bandes étaient présentes. À travers le jeu, le personnage en rencontre plusieurs.
New Austin
Cette région, composée des comtés de Hennigan's Stead, Cholla Springs, Gaptooth Ridge et Rio Bravo, est sans doute la plus dangereuse de toutes. En effet, on peut distinguer quatre grandes bandes, chacune ayant un repaire dans un des quatre comtés.
- La Bande des jumeaux Bollard : Cette bande de voleurs de bétails est dirigée par les jumeaux Ike et Willie Bollard et sévit dans le comté de Hennigan's Stead et parfois dans celui de Cholla Springs. Leur repaire se situe au cœur du canyon de Pike's Basin. On y va pour la première fois durant la mission "Règlements de comptes à Pike's Basin", en compagnie du Marshal Johnson et de ses deux adjoints, Eli et Jonah, afin de libérer des fermiers kidnappés ainsi que leur troupeau. Bonnie MacFarlane se plaint de cette bande en raison des vols qu'elle commet. Les membres de la bande portent un foulard rouge autour du cou, des jambières de cuir ou des pantalons d'équitation et certains ont un lasso en bandouillère. Ils peuvent être croisés au saloon de Thieves' Landing, où ils flânent et boivent.
- La Bande de Walton : Cette bande de bandits de grand chemin est dirigé par Walton Lowe, qui est capturé ou tué par John Marston et le Marshal Johnson à Pleasance House, durant la mission "Politique à Armadillo". Les membres de cette bande sont reconnus pour semer la panique dans le comté de Cholla Springs, mais également dans le comté de Gaptooth Ridge et parfois de Rio Bravo. Leur repaire se situe à Twin Rocks. Les membres de la bande sont facilement reconnaissables grâce à leurs chapeaux haut-de-forme et leurs pantalons rapiécés, qu'ils portent dans leurs bottes. On les rencontre souvent au saloon d'Armadillo.
- La bande de chasseur de trésor : On ne connait pas l'identité des chefs de cette bande de bandits qui sévit dans le comté de Gaptooth Ridge. Leur repaire se situe dans la mine désaffectée de Gaptooth Breach. Cette bande s'attaque à John Marston et à Seth Briars durant les missions "Petite promenade entre amis" et "Laissez les morts s'enterrer eux-mêmes", lorsque ce dernier recherche son trésor à Tumbleweed. Durant la mission de l'Irlandais "Des soucis et des hommes", John s'attaque à eux à la mine afin de récupérer une mitrailleuse Gatling pour préparer l'attaque de Fort Mercer. Les membres de la bande sont repérables grâce à leurs habits crasseux et déchirés.
Bill Williamson
- La Bande de Williamson : Cette bande de bandit, présente seulement durant le premier chapitre de l'histoire, est dirigée par Bill Williamson, ancien frère d'arme de John Marston lorsqu'ils étaient dans la Bande de Dutch Van der Linde. Elle occupait Fort Mercer, un ancien fort abandonné durant la guerre mexicaine. La bande est connue dans tout New Ausin pour avoir causé de nombreux massacres sanglants. Dans la mission "Qui aime bien descend bien", John et le Marshal Johnson, accompagnés des adjoints et d'un autre shériff, découvrent avec horreur le massacre de la ferme de Ridgewood par les hommes de Williamson. Norman Deek, le bras droit de Bill, sera capturé par John à Mercer Station après une violente fusillade. La bande est également responsable de la capture de Bonnie MacFarlane et la tentative de pendaison qui suivit à Tumbleweed. Elle fut anéantie lors de l'attaque de Fort Mercer.
West Elizabeth
Cette région est constituée des comtés de Great Plains et de Tall Trees. Seule la Bande de Dutch y sévit.
Dutch van der Linde
- La Bande de Dutch van der Linde : Dutch est le leader de cette bande, majoritairement composée d'Américains natifs qui désirent se venger des horreurs qui ont été commises envers leurs ancêtres durant la conquête de l'Ouest, de nombreuses décennies auparavant. Le repaire de Dutch et ses hommes se situe dans la réserve de Cochinay, dans le comté de Tall Trees, où ils y ont construit une véritable forteresse. Ils sèment la panique dans tout West Elizabeth, attaquant tous ceux et celles qui ont la malchance de croiser leur chemin. Leur repaire sera déserté lorsque John règlera ses comptes avec Dutch.
Nuevo Paraiso
Cette région est composée de trois comtés, Punta Orgullo, Perdido et Diez Coronas. Deux groupes sévissent dans la région. La Bande des Banditos et les Rebelles de Reyes.
- La Bande des Banditos : Les Banditos constituent la seule bande de bandits dans la région de Nuevo Paraiso. On ne connait pas le nom du leader de cette bande. Leur repaire se situe dans la forteresse abandonnée de Fort Mercer, une fois la bande de Williamson anéantie. Malgré la Révolution mexicaine présente dans le jeu, les Banditos ne prennent pas parti. Ils apparaissent pendant l'histoire seulement durant la mission "La tragédie du pistolero", lorsque John et Landon Ricketts interviennent durant une attaque de fourgon de la banque de Chuparosa. Les membres de cette bande portent un foulard rouge, un large chapeau, un veston et ils ont une cartouchière, parfois deux. Ils boivent dans la cantina de Chuparosa et le soir à Casa Madrugada.
- Les de Reyes : Cette bande, dirigée par Abraham Reyes, ne s'attaque pas à la population. Elle vise les troupes du président, le Général Sanchez, durant la révolution. Son repaire se situe à Nosalida. Les rebelles sont reconnaissables grâce à leur poncho rayé, souvent bleu et gris, leur cartouchière et leur tête découverte. On peut les rencontrer à Agave Viejo et, une fois la révolution terminée, à Escalera. Suite au renversement du gouvernement, ils prennent la place des Représentants de la loi mexicaine et se chargeront d'arrêter John s'il commet des crimes.
En général :
Les Criminels ne sont pas considérés comme une bande à part entière. Ils ont le repaire de Tumbleweed aux États-Unis et le repaire de Tesoro Azul au Mexique. Les Criminels blancs se tiennent beaucoup à Thieves' Landing.
Elles ne constituent pas une menace "terrible" envers le joueur. Si John tue un de leurs membres, aucune sanction juridique ne peut lui être attitrée. Toutefois, ils peuvent vous attaquer par surprise en tendant des embuscades à l'écart des villes.
Si le joueur nettoie tous les repaires de New Austin (Pike's Basin, Twin Rocks, Gaptooth Breach, Tumbleweed et Fort Mercer) en moins de 24 heures, alors la tenue d'US Marshal sera disponible parmi les autres tenues .