Заснована у 1711 році після зруйнування царським військом у 1709 році старої Чортомлицької Січі (приводом для цього послужив перехід її останнього кошового К. Гордієнка з частиною козаків на бік Карла XII) запорожці спробували влаштувати Січ на р. Кам'янці. Але Петро І, вбачаючи загрозу в козацькій організації, заборонив її. Тоді запорожці з дозволу кримського хана заснували Січ на його землях, в урочищі Олешки (пониззя Дніпра, навпроти сучасного міста Херсона). Спершу територія Олешківської Січі була незначною, з 1712 року, після поразки Росії у війні з Туреччиною, запорозькі володіння поширилися на північ до річок Орель та Самара.
Щоб нейтралізувати грізну військову силу запорожців, хан заборонив їм споруджувати укріплення й мати артилерію. Уряд у Бахчисараї використовував їх на виснажливих земляних роботах на Перекопі та в ін. місцях, обклав непосильними податками. Все це викликало масове невдоволення.
Загалом, Січ являла собою правильний чотирикутник з ровами й валами заввишки 1,5 метри, з редутами по кутах та брамою з північного боку. У центрі розташовувалися курені-напівземлянки (вони досліджувалися археологами у 1990-2003 роках). На захід від коша стояла церква Покрови Пресвятої Богородиці, зроблена з очерету і на вигляд майже не відрізнялася від куреня, біля якої був цвинтар та криниця, де ніколи не замерзала вода. Січ займала площу щонайбільше 2 гектари, це був майже правильний; чотирикутник, обнесений ровами й валами та дерев'яним частоколом. Оборонний комплекс цієї Січі доповнювали 4 редути, в кожному з кутів форту.
З осені 1711 р., після повернення більшості запорожців з Бессарабії, де вони знаходились з військами шведського короля, олешківське поселення набуває рис, притаманних власне Січі. Від цього моменту кількість його мешканців зросла до 6 тис. осіб, самих тільки нежонатих козаків. При цьому багато січовиків ще перебувало у Буджаку та навіть у Валахії. Саме з цього часу починається зведення ровів та валів, адміністративних споруд та куренів, церкви.
Угодою гетьмана П. Орлика з турецьким урядом від 22 квітня 1714р. було остаточно визначено політичний статус Війська Запорозького в Османській імперії (Кримському ханстві): воно відтепер перебувало у подвійній залежності від Османів та Гіреїв; за участь у військових виправах кримських ханів запорожцям було обіцяно невтручання у їхні внутрішні справи, даровано податкові пільги та право займатися їхніми традиційними промислами на всій території Кримського ханства.
В тому ж 1714 р. І. Малашевич, обраний кошовим замість К Гордієнка, звернувся до царського уряду з проханням дозволити запорожцям повернутися на старі місця. Адміністрація Петра І зволікала з відповіддю, не бажаючи псувати стосунки з кримським ханом, за спиною якого стояла Туреччина. У травні 1728 р. повсталі козаки скинули Гордієнка, що перед тим повернув собі посаду кошового, й рушили в Україну. Однак лише 1734 р. у зв'язку з наближенням війни з Туреччиною російський уряд дозволив їм заснувати на р. Підпільній Нову Січ.
