Это зависит от сервиса, который используется для общения, его архитектуры.
Чаты бывают такими, что сообщения хранятся исключительно в клиенских приложениях на компьютерах собеседников, но большинство приложений и сервисов используют сервер для синхронизации сообщений между клиентами и оффлайн-сообщений, например Skype или VK. На самом деле по нажатию на кнопку удаления истории происходит то, что решит программист. Может удаляться история на одном из клиентов, на сервере, даже на чужом клиенте. А может не удаляться, а просто прятаться от ваших глаз.
Если переписка лежит только на вашем компьютере, то при удалении обычно будет удалён файл с ней. Если бы к вам пришли из ФСБ, например, и конфисковали устройство, то у них были бы шансы этот файл восстановить. В свою очередь, при наличии технических навыков можно этот шанс заранее свести к нулю, но здесь уже нажатием кнопки удаления истории не обойтись.
Если переписка находится на сервере, то сложно сказать, были ли удалены на самом деле сообщения, или просто они теперь не отображаются. Сотрудник компании, по злому умыслу и/или по требованию правоохранительных органов эти данные тоже может попытаться восстановить. Насколько это сложно, зависит, опять же, от внутреннего устройства системы. Могут и в свободном внутреннем доступе оказаться.
Так что шанс восстановления во всех этих случаях остаётся ненулевым, хотя часто требуются определённые навыки и влияние. Однако данный вопрос всё равно слишком общий, в зависимости от конкретного сервиса можно дать более точный ответ.