Сын Скилура Палак продолжал внешнюю политику своего отца. Во время его правления участились вооруженные столкновения с Херсонесом, которые постепенно перешли в открытые военные действия. Отряды скифов подступили к стенам Херсонеса. Это вынудило его жителей обратиться за помощью к понтийскому царю Митридату Евпатору, который стал на сторону Херсонеса и Боспора.
Война велась с переменным успехом. Наконец, Диофанту, полководцу Митридата, удалось нанести решительное поражение Палаку, выступавшему в союзе с роксоланами. Войска Диофанта овладели скифскими крепостями Хабеями и Неаполем. Херсонес и Боспор признали протекторат Понтийского царства.
Немного позднее Рим одержал победу над войсками Митридата и с 63 г. до н. э. установил контроль над Боспором.
После поражения в войне Скифское царство в Крыму переживает временный упадок. От него отпала Ольвия. Боспор прекращает платить дань. С подчинением античных городов могущественной Римской империи скифы, ослабленные в борьбе с Диофантом, не в силах уже были продолжать на них активное наступление. Возможно, их отдельные разрозненные группы еще совершали набеги на соседние греческие города, о чем может свидетельствовать сооружение боспорским царем Асандром в конце I в. до н. э. земляного вала для защиты западных границ своего государства. Но никаких сведений о важных событиях в жизни Скифского государства и его политических деятелей в источниках этого времени нет. По-видимому, скифы постепенно накапливали силы после поражения, нанесенного им Диофантом. В I в. н. э. они опять предпринимают военные действия против Ольвии, Херсонеса и Боспора.
Ольвия снова попадает в зависимость от Скифского царства. Заинтересованные в торговле скифы принимают участие в ее восстановлении после гетского разгрома. В правление Фарзоя и Инисмея, чеканивших в течение 35–45 гг. в Ольвии золотые и серебряные монеты, наблюдается новый политический и экономический подъем Скифского государства. Подтверждением этому могут служить монеты, надписи и археологические материалы.
В долинах рек, на возвышенных местах в Крыму возникает большая сеть укрепленных поселений и селищ. Названия шести городов и целого ряда других населенных пунктов приводит Плиний Старший (I в. н. э.), который Малую Скифию именует Таврикой. Он отмечает, что внутри страны живет 23 племени, а по горному хребту — скифо-тавры, что указывает на происшедшее этническое их смешение. В это время на Перекопском перешейке был сооружен ров и вал. Там, по Плинию, находился город Тафры. В наше время в Крыму открыто 34 городища и почти столько же селищ. Они расположены главным образом в предгорьях центральной и юго-западной части Крыма. Большинство из них относится к первым векам н. э.
Столица скифов — Неаполь скифский укрепляется новыми панцирными стенами. В нем сооружаются новые здания с фресками в стиле боспорской живописи. На северной окраине появляются вырубленные в скалах семейные усыпальницы для царских дружинников и их семей.
В первых веках нашей эры снова устанавливаются тесные связи скифов с южнопонтийскими центрами. Из них в Неаполь скифский доставлялись черепица, амфоры, краснолаковая посуда, разные металлические изделия и украшения. Значительное место в торговле Неаполя занимала херсонесская продукция. Возобновляются торговые связи с Ольвией. Как сообщает Дион Хрисостом (I — начало II в. н. э.), «Ольвия продавала соль большинству варваров, а также эллинам и скифам, живущим на Таврическом полуострове». Оживляется товарообмен между Ольвией и нижнеднепровскими укрепленными поселениями. На рубеже нашей эры здесь получает развитие каменное домостроительство; проводится частичная реконструкция и дополнительное укрепление оборонительных стен. Увеличивается приток краснолаковых изделий из Пергама, Самоса, а также местных ольвийских изделий и завоз вина и оливкового масла из южнопонтийских центров.
Укрепив свои политические и экономические позиции во время правления Фарзоя, скифы возобновляют наступление на Херсонес. Они вторично отнимают у него Калос Лимен и Керкенитиду, которые Арриан называет уже «скифскими крепостями». Это вынуждает Херсонес обратиться за помощью на этот раз к Риму. В 62 г. н. э. Нерон высылает в Крым военную экспедицию во главе с легатом (правителем) Нижней Мезии Плавтием Сильваном. Последний отразил натиск скифов, но Херсонес поплатился за это своей независимостью, подпав под власть Рима.