diff --git a/src/gfx_layout.h b/src/gfx_layout.h
--- a/src/gfx_layout.h
+++ b/src/gfx_layout.h
@@ -16,6 +16,9 @@
 #include "gfx_func.h"
 #include "core/smallmap_type.hpp"
 
+#include <map>
+#include <string>
+
 #ifdef WITH_ICU
 #include "layout/ParagraphLayout.h"
 #define ICU_FONTINSTANCE : public LEFontInstance
@@ -32,6 +35,7 @@ struct FontState {
 	TextColour cur_colour;   ///< Current text colour.
 	TextColour prev_colour;  ///< Text colour from before the last colour switch.
 
+	FontState() : fontsize(FS_END), cur_colour(TC_INVALID), prev_colour(TC_INVALID) {}
 	FontState(TextColour colour, FontSize fontsize) : fontsize(fontsize), cur_colour(colour), prev_colour(colour) {}
 
 	/**
@@ -143,10 +147,11 @@ public:
 	};
 
 	const WChar *buffer_begin; ///< Begin of the buffer.
-	WChar *buffer;             ///< The current location in the buffer.
+	const WChar *buffer;       ///< The current location in the buffer.
 	FontMap &runs;             ///< The fonts we have to use for this paragraph.
 
 	ParagraphLayout(WChar *buffer, int length, FontMap &runs);
+	void reflow();
 	Line *nextLine(int max_width);
 };
 #endif /* !WITH_ICU */
@@ -166,7 +171,36 @@ class Layouter : public AutoDeleteSmallV
 	size_t AppendToBuffer(CharType *buff, const CharType *buffer_last, WChar c);
 	ParagraphLayout *GetParagraphLayout(CharType *buff, CharType *buff_end, FontMap &fontMapping);
 
-	CharType buffer[DRAW_STRING_BUFFER]; ///< Buffer for the text that is going to be drawn.
+	/** Key into the linecache */
+	struct LineCacheKey {
+		FontState state_before;  ///< Font state at the beginning of the line.
+		std::string str;         ///< Source string of the line (including colour and font size codes).
+
+		/** Comparison operator for std::map */
+		bool operator<(const LineCacheKey &other) const
+		{
+			if (this->state_before.fontsize != other.state_before.fontsize) return this->state_before.fontsize < other.state_before.fontsize;
+			if (this->state_before.cur_colour != other.state_before.cur_colour) return this->state_before.cur_colour < other.state_before.cur_colour;
+			if (this->state_before.prev_colour != other.state_before.prev_colour) return this->state_before.prev_colour < other.state_before.prev_colour;
+			return this->str < other.str;
+		}
+	};
+	/** Item in the linecache */
+	struct LineCacheItem {
+		/* Stuff that cannot be freed until the ParagraphLayout is freed */
+		CharType buffer[DRAW_STRING_BUFFER]; ///< Accessed by both ICU's and our ParagraphLayout::nextLine.
+		FontMap runs;                        ///< Accessed by our ParagraphLayout::nextLine.
+
+		FontState state_after;   ///< Font state after the line.
+		ParagraphLayout *layout; ///< Layout of the line.
+
+		LineCacheItem() : layout(NULL) {}
+		~LineCacheItem() { delete layout; }
+	};
+	typedef std::map<LineCacheKey, LineCacheItem> LineCache;
+	static LineCache linecache;
+
+	static LineCacheItem &GetCachedParagraphLayout(const char *str, size_t len, const FontState &state);
 
 	typedef SmallMap<TextColour, Font *> FontColourMap;
 	static FontColourMap fonts[FS_END];
@@ -177,6 +211,8 @@ public:
 	Dimension GetBounds();
 
 	static void ResetFontCache(FontSize size);
+	static void ResetLineCache();
+	static void ReduceLineCache();
 };
 
 #endif /* GFX_LAYOUT_H */