У річницю вбивства Олександра II — 1 березня 1882 р. — невелика група семінаристів на чолі з О. Саліковським, якому ректор семінарії дав прізвисько «генерала соціалістичної пропаганди», зібралася на околиці міста на сходку. Тут було організовано «Подільську дружину» і прийнято відозву, в якій схвалювалося вбивство «царя-ката», прославлялись герої «Народної волі» — Кибальчич, Рисаков, Перовська та ін. Зачитали статтю з «Народної волі» та програму «Чорного переділу». Але про діяльність «Подільської дружини» скоро дізналася поліція, почалися арешти, слідство. Коцюбинський не був присутній на цій сходці, проте з членами дружини, зокрема О. Саліковським, був добре знайомий і підтримував стосунки.
Одного разу, вертаючись увечері додому, як згадував пізніше Хома Коцюбинський, Михайло Михайлович помітив підозрілу людину, що заглядала у вікна його хати. Не довго думаючи, він підбіг і вдарив незнайомця своїм сукуватим ціпком. Ним виявився жандарм-вартовий, що разом з іншими прийшов на квартиру Коцюбинського робити трус. Михайла Михайловича заарештували, звинувативши в нападі на поліцію. Але через три дні відпустили. Коли згодом він потрапив під нагляд поліції, про цю справу вже забули, але для Коцюбинського це перше знайомство з в’язницею, де він просидів три дні, надовго відклалося в пам’яті.
Літературна кар’єра Коцюбинського почалася з цілковитого провалу. Повернувшись у Вінницю, Михайло Михайлович дає уроки, щоб заробити трохи грошей на підтримку сім’ї, в якій було п’ятеро дітей: Михайло, Ліда, Хома, Леонід і Ольга. Часом він виїжджає в село, щоб навчати панських дітей. Ночами (бо вдень не було часу) просиджує над книжками. Читає багато з російської і зарубіжної літератур: Успенського і Некрасова, Достоєвського і Салтикова-Щедріна, Золя і Сенкевича. Особливе захоплення викликали твори українських письменників — Шевченка, Марка Вовчка, Куліша, Нечуя-Левицького, Кропивницького та ін. Любить читати напам’ять поезії з «Кобзаря», а найбільше «І мертвим, і живим, і ненарожденним землякам моїм в Украйні і не в Украйні моє дружнєє посланіє... »
У 1884 р. Коцюбинський пробує написати оповідання, яке відоме під назвою «Андрій Соловійко, або Вченіє світ, а невченіє тьма». У Вінниці Михайло Коцюбинський товаришує із священиком П. І. Вікулом, двоюрідним братом О. Саліковського, який учив їх обох у Шаргородському духовному училищі. П. І. Вікул підтримував зв’язки з революційно налаштованою молоддю, а в його домі часто збиралася прогресивна інтелігенція. Бував тут і місцевий присяжний уповноважений Нейман — людина освічена і з великими симпатіями до української літератури. Через Вікула оповідання Коцюбинського «Андрій Соловійко...» було передано на суд Нейману. Вирок був дуже суворий. Зверхньо оцінивши першу спробу молодого автора, Нейман у кінці відгуку радив Коцюбинському кинути цю справу, аби «не калічити святу нашу мову».
Присуд Неймана не спинив Михайла Михайловича, і протягом наступних 2—3 років він створює нові оповідання («21-го грудня, на Введеніє», «Дядько та тітка»), але показувати їх комусь чи подавати до друку не наважується. А згодом і зовсім замовкає на кілька років, очевидно вражений своїм невдалим дебютом.
За життя Коцюбинський ніколи не друкував ці перші твори. З’являлися його збірки, окремі твори і вибране, виходили різними мовами в Росії і за кордоном, але учнівські спроби так і пролежали невідомими широкому читачеві, аж поки не побачили світ років через десять після смерті письменника.
11 червня 1890 р. начальник Подільського жандармського управління у відношенні до департаменту поліції повідомляє, що київський губернатор видав Михайлові Коцюбинському закордонний паспорт і наказує встановити нагляд за поверненням Коцюбинського в межі імперії. Зважившись виїхати до Львова, Михайло Михайлович виявив неабияку сміливість, адже Галичина належала до Австро-Угорщини і вважалась чи не центром українського культурного руху. Безпосереднім приводом до поїздки за кордон послужила перша публікація Коцюбинського — поява у львівському журналі «Дзвінок» його вірша «Наша хатка». Тут у Львові він зав’язує контакти з редакторами українських журналів «Дзвінок», «Правда», «Зоря», що мали ліберально-народницький напрям, знайомиться з Іваном Франком.