\documentclass[a4paper]{report}
\usepackage[utf8x]{inputenc}
\begin{document}
\tableofcontents
\chapter{ø}
\end{document}


First time I compile this, I get an ø in the table of contents. Second time I compile this, the ø turns into [Pleaseinsertintopreamble], and this goes on and on.

What should I do in order to get an ø every time?

Like Harish I would suggest to use utf8 instead of ucs/utf8x, but if for some reason you really need utf8x you must prerender the offending unicode character:

\documentclass[a4paper]{report}
\usepackage[T1]{fontenc}
\usepackage[utf8x]{inputenc}
\PrerenderUnicode{ø}
\begin{document}
\tableofcontents
\chapter{ø}
\end{document}

• Perfect, the thing is I do need utf8x – Coolwater Apr 27 '15 at 9:01
• Why do you need it? – Ulrike Fischer Apr 27 '15 at 9:03
• I use package "alltt" to include txt-files with æøå, which fails with utf8 – Coolwater Apr 27 '15 at 9:06
• I don't see a reason why these chars should fail, you should better ask about it in a new question (with an example). – Ulrike Fischer Apr 27 '15 at 9:22
• @Coolwater Notepad is known for adding the BOM to its UTF-8 encoded files and that is the cause of your problem. See UTF-8 encoding and Notepad with LaTeX Better cure the disease than just the symptoms. – egreg Apr 27 '15 at 15:10

Use \usepackage[utf8]{inputenc} instead of utf8x

\documentclass[a4paper]{report}
\usepackage[utf8]{inputenc}
\begin{document}
\tableofcontents
\chapter{ø}
\end{document}