В это время Дэн Настаси заявил, что не может отправиться с группой в турне на длительный промежуток времени, по семейным и деловым обстоятельствам. Шон начал искать нового гитариста, и пригласил в Dog Eat Dog своего старого друга Кевина Мейю, из группы Cro-Mags.

Так с новым альбомом, находящимся в продаже группа намеревалась вновь отправиться в турне по Европе, на сей раз разогревая своих старых друзей из группы Biohazard. Biohazard также как и Bad Brains, оказывали всяческую дружескую поддержку Dog Eat Dog во время гастролей. Однако, во время тура Dog Eat Dog стали хедлайнерами вместе с Biohazard. Это был огромный успех для группы. Dog Eat Dog получали всё большее признание и с каждым концертом у них появлялись всё новые поклонники. All Boro Kings разошёлся тиражом в более 600 000 копий, а видео на песню No Fronts попало в тяжёлую ротацию MTV. По возвращении с гастролей Кевин Мейю, покинул группу ради создания своего нового проекта под названием White Devil. Dog Eat Dog никогда не были группой, которая размещала бы объявления о поисках нового музыканта в газете, они всегда искали его среди друзей. Новым участником группы стал Марк Де Бэкер. Марк на протяжении долгого времени был басистом в Mucky Pup, по сути являясь профессиональным гитаристом. В это же время Дэвид Мэлтби, также оставил группу. Он объяснил это тем, что исполнил свою мечту, участвуя в мировом турне вместе с рок-группой. После этого он захотел стремиться в своей жизни к чему-нибудь другому. Группа пожелала ему дальнейших успехов и они расстались. Нынче он играет в группе The Shining Path вместе с Дэррилом Дженнифер и участниками команды Roguish Armament. Место барабанщика занял Брендон Финли, который не только оправдал, но и превзошёл все ожидания группы от его способностей. Будучи не только феноменальным барабанщиком и ветераном гастрольных поездок, он оказался большим знатоком пива. В конце 1995 года группа получила награду MTV Europe Music Awards в номинации «Лучший дебют». Это было большим вознаграждением со стороны зрителей для Dog Eat Dog, которые так много трудились. Для группы это стало большой неожиданностью, ведь они обошли таких серьёзных конкурентов как Аланис Мориссетт и Weezer. Награду они получили из рук Майка Хатчинса из группы INXS. В то время как у себя на Родине группа играла в маленьких клубах, в Европе Dog Eat Dog выступали на крупных фестивалях, включая Dynamo Open Air в 1995 году, выступление на котором впоследствии вышло на DVD.

Play Games (1996—1999)

После возвращения домой группа засела за написание нового альбома. Не сочиняя новых песен после продолжительного турне, группа долго сидела на одном месте. Но после летних фестивалей Roadrunner Records затребовали нового сингла к весне следующего года. И парни отправились в студию с ещё не до конца подготовленным материалом.

Дописывать тексты приходилось в студии, иногда записывали первое что приходило на ум. В одной из таких записей парни спели, что хотят записать песню вместе с легендарным Ронни Джеймсом Дио. Об этом узнали люди с лейбла Roadrunner Records, и восприняли эту идею с энтузиазмом. Сказано — сделано. Сам Дио обрадовался этой идее и записал с Dog Eat Dog песню. Они вместе хорошо провели время. Это был большой опыт для Dog Eat Dog. Ещё одну песню ребята записали с RZA из группы Wu-Tang Clan. Dog Eat Dog и RZA имели общего продюсера и в его офисе начали обсуждать музыку. Джон давно интересовался работой с хип-хоп артистами, а RZA был рад поработать с живой рок-группой. После нескольких телефонных звонков они собрались в студии в Нью-Йорке, и после нескольких часов совместной работы родилась песня «Step Right In». Первую половину альбома Dog Eat Dog записали с «Butcher Brothers», Филом и Джо Николо. Они уже спродюсировали мультиплатиновые альбомы групп Cypress Hill, The Fugees, Urge Overkill… Работа с новыми продюсерами открыла для группы новые просторы для творчества. Вторую часть альбома группа записывала у себя дома, в Нью-Йорке вместе с продюсером Бобом Муссо. Боб известен своей работой с такими группами, как Murphy’s Law и Praxis. Альбом был назван Play Games, и был закончен в установленный срок — летом 1996 года. После выхода второй пластинки, Dog Eat Dog готовы были отправиться в очередное турне. На сей раз группа побывала в тех странах, в которых не бывала прежде. Группа сделала широкомасштабный тур по странам Азии и Южной Америки. Dog Eat Dog выступили в более чем 35 странах.