В январе 1894 года Меньшиков был приглашен в дом Толстого в Москве. Толстой записал в дневнике: "Познакомился... с Волкенштейном и Меньшиковым: оба хорошие, добрые, умные последователи - особенно Меньшиков".
Отношения Меньшикова с Толстым, продолжавшиеся практически до конца жизни последнего, за пятнадцать с лишним лет претерпели существенные изменения. Сначала Меньшиков сам причислял себя к "толстовцам", помогал Толстому в организации помощи голодающим (1898 г.), выполнял его издательские поручения. Затем, когда философия, общественные позиции Толстого стали изменяться все более и более в сторону конфронтации с интересами государства, церкви, армии, Меньшиков не принял этих метаморфоз и счел своим долгом резко полемизировать с Толстым и окружавшими его "последователями". Однако Меньшиков всегда преклонялся перед гением Толстого-художника, любил его как великого и глубоко несчастного человека.
В самом конце 1891 года Меньшиков познакомился с Антоном Павловичем Чеховым.
Они были почти ровесниками. Меньшиков тогда еще носил морскую форму, и Чехов звал его "Морячок". Отношениям Меньшикова и Чехова, отличавшимся порою особенной теплотой, также суждено было продлиться до последних лет короткой жизни Чехова. За годы их знакомства они отправили друг другу примерно по полусотне писем. Письма Чехова к Меньшикову не раз публиковались в полных собраниях сочинений писателя. Письма Меньшикова хранятся в архивах.
Незадолго до своей смерти, в сентябре 1918 года, Меньшиков пишет в дневнике: "Никого я так не любил в жизни, как Толстого и Чехова..."
На рубеже веков "Неделя" прекратила свое существование. Сотрудники издательства должны были искать новую работу. Так получилось, что Меньшиков после некоторых колебаний связал свою судьбу с газетой Алексея Сергеевича Суворина "Новое время", где, как известно, сотрудничали и Антон Чехов, и его старший брат Александр, и популярный тогда и сейчас В. В. Розанов, и многие другие известные журналисты и писатели.
Меньшиков был ведущим публицистом "Нового времени" с 1901 по 1917 год. Он вел в газете рубрику "Письма к ближним", публикуя еженедельно по две-три статьи, не считая больших воскресных фельетонов (так назывались тогда особенно острые, порою весьма серьезные материалы на темы дня). Меньшиков комплектовал затем свои статьи и фельетоны из рубрики "Письма к ближним" и выпускал их отдельными ежемесячными журнально-дневниковыми книжками.
