Index: src/OFMutableString.m
==================================================================
--- src/OFMutableString.m
+++ src/OFMutableString.m
@@ -293,10 +293,13 @@
 }
 
 - removeCharactersFromIndex: (size_t)start
 		    toIndex: (size_t)end
 {
+	start = of_string_index_to_position(string, start, length);
+	end = of_string_index_to_position(string, end, length);
+
 	if (start > end)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
 	if (end > length)

Index: src/OFString.h
==================================================================
--- src/OFString.h
+++ src/OFString.h
@@ -22,10 +22,12 @@
 	OF_STRING_ENCODING_WINDOWS_1252
 };
 
 extern int of_string_check_utf8(const char*, size_t);
 extern size_t of_string_unicode_to_utf8(uint32_t, char*);
+extern size_t of_string_position_to_index(const char*, size_t);
+extern size_t of_string_index_to_position(const char*, size_t, size_t);
 
 /**
  * A class for managing strings.
  */
 @interface OFString: OFObject <OFCopying, OFMutableCopying>

Index: src/OFString.m
==================================================================
--- src/OFString.m
+++ src/OFString.m
@@ -137,10 +137,35 @@
 		return 4;
 	}
 
 	return 0;
 }
+
+size_t
+of_string_position_to_index(const char *str, size_t pos)
+{
+	size_t i, idx = pos;
+
+	for (i = 0; i < pos; i++)
+		if (OF_UNLIKELY((str[i] & 0xC0) == 0x80))
+			idx--;
+
+	return idx;
+}
+
+size_t
+of_string_index_to_position(const char *str, size_t idx, size_t len)
+{
+	size_t i;
+
+	for (i = 0; i <= idx; i++)
+		if (OF_UNLIKELY((str[i] & 0xC0) == 0x80))
+			if (++idx > len)
+				return SIZE_MAX;
+
+	return idx;
+}
 
 @implementation OFString
 + string
 {
 	return [[[self alloc] init] autorelease];
@@ -519,11 +544,11 @@
 	if (str_len > length)
 		return SIZE_MAX;
 
 	for (i = 0; i <= length - str_len; i++)
 		if (!memcmp(string + i, str_c, str_len))
-			return i;
+			return of_string_position_to_index(string, i);
 
 	return SIZE_MAX;
 }
 
 - (size_t)indexOfLastOccurrenceOfString: (OFString*)str
@@ -531,18 +556,18 @@
 	const char *str_c = [str cString];
 	size_t str_len = [str cStringLength];
 	size_t i;
 
 	if (str_len == 0)
-		return length;
+		return of_string_position_to_index(string, length);
 
 	if (str_len > length)
 		return SIZE_MAX;
 
 	for (i = length - str_len;; i--) {
 		if (!memcmp(string + i, str_c, str_len))
-			return i;
+			return of_string_position_to_index(string, i);
 
 		/* Did not match and we're at the last char */
 		if (i == 0)
 			return SIZE_MAX;
 	}
@@ -549,10 +574,13 @@
 }
 
 - (OFString*)substringFromIndex: (size_t)start
 			toIndex: (size_t)end
 {
+	start = of_string_index_to_position(string, start, length);
+	end = of_string_index_to_position(string, end, length);
+
 	if (start > end)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
 	if (end > length)

Index: tests/string.m
==================================================================
--- tests/string.m
+++ tests/string.m
@@ -113,39 +113,39 @@
 
 	TEST(@"-[appendWithFormat:]",
 	    [([s[0] appendWithFormat: @"%02X", 15]) isEqual: @"test: 1230F"])
 
 	TEST(@"-[indexOfFirstOccurrenceOfString:]",
-	    [@"foo" indexOfFirstOccurrenceOfString: @"oo"] == 1 &&
-	    [@"foo" indexOfFirstOccurrenceOfString: @"o"] == 1 &&
-	    [@"foo" indexOfFirstOccurrenceOfString: @"f"] == 0 &&
-	    [@"foo" indexOfFirstOccurrenceOfString: @"x"] == SIZE_MAX)
+	    [@"𝄞öö" indexOfFirstOccurrenceOfString: @"öö"] == 1 &&
+	    [@"𝄞öö" indexOfFirstOccurrenceOfString: @"ö"] == 1 &&
+	    [@"𝄞öö" indexOfFirstOccurrenceOfString: @"𝄞"] == 0 &&
+	    [@"𝄞öö" indexOfFirstOccurrenceOfString: @"x"] == SIZE_MAX)
 
 	TEST(@"-[indexOfLastOccurrenceOfString:]",
-	    [@"foo" indexOfLastOccurrenceOfString: @"oo"] == 1 &&
-	    [@"foo" indexOfLastOccurrenceOfString: @"o"] == 2 &&
-	    [@"foo" indexOfLastOccurrenceOfString: @"f"] == 0 &&
-	    [@"foo" indexOfLastOccurrenceOfString: @"x"] == SIZE_MAX)
+	    [@"𝄞öö" indexOfLastOccurrenceOfString: @"öö"] == 1 &&
+	    [@"𝄞öö" indexOfLastOccurrenceOfString: @"ö"] == 2 &&
+	    [@"𝄞öö" indexOfLastOccurrenceOfString: @"𝄞"] == 0 &&
+	    [@"𝄞öö" indexOfLastOccurrenceOfString: @"x"] == SIZE_MAX)
 
 	TEST(@"-[substringFromIndexToIndex:]",
-	    [[@"foo" substringFromIndex: 1
-				toIndex: 2] isEqual: @"o"] &&
-	    [[@"foo" substringFromIndex: 3
+	    [[@"𝄞öö" substringFromIndex: 1
+				toIndex: 2] isEqual: @"ö"] &&
+	    [[@"𝄞öö" substringFromIndex: 3
 				toIndex: 3] isEqual: @""])
 
 	EXPECT_EXCEPTION(@"Detect out of range in "
 	    @"-[substringFromIndex:toIndex:] #1", OFOutOfRangeException,
-	    [@"foo" substringFromIndex: 2
+	    [@"𝄞öö" substringFromIndex: 2
 			       toIndex: 4])
 	EXPECT_EXCEPTION(@"Detect out of range in "
 	    @"-[substringFromIndex:toIndex:] #2", OFOutOfRangeException,
-	    [@"foo" substringFromIndex: 4
+	    [@"𝄞öö" substringFromIndex: 4
 			       toIndex: 4])
 
 	EXPECT_EXCEPTION(@"Detect start > end in "
 	    @"-[substringFromIndex:toIndex:]", OFInvalidArgumentException,
-	    [@"foo" substringFromIndex: 2
+	    [@"𝄞öö" substringFromIndex: 2
 			       toIndex: 0])
 
 	TEST(@"-[stringByAppendingString:]",
 	    [[@"foo" stringByAppendingString: @"bar"] isEqual: @"foobar"])
 
@@ -182,17 +182,36 @@
 	EXPECT_EXCEPTION(@"Detect invalid encoding in -[stringByURLDecoding] "
 	    @"#2", OFInvalidEncodingException,
 	    [@"foo%FFbar" stringByURLDecoding])
 
 	TEST(@"-[removeCharactersFromIndex:toIndex:]",
-	    (s[0] = [OFMutableString stringWithString: @"fooobar"]) &&
+	    (s[0] = [OFMutableString stringWithString: @"𝄞öööbä€"]) &&
 	    [s[0] removeCharactersFromIndex: 1
 				    toIndex: 4] &&
-	    [s[0] isEqual: @"fbar"] &&
+	    [s[0] isEqual: @"𝄞bä€"] &&
 	    [s[0] removeCharactersFromIndex: 0
 				    toIndex: 4] &&
 	    [s[0] isEqual: @""])
+
+	EXPECT_EXCEPTION(@"Detect OoR in "
+	    @"-[removeCharactersFromIndex:toIndex:] #1", OFOutOfRangeException,
+	    {
+		s[0] = [OFMutableString stringWithString: @"𝄞öö"];
+		[s[0] substringFromIndex: 2
+				 toIndex: 4];
+	    })
+
+	EXPECT_EXCEPTION(@"Detect OoR in "
+	    @"-[removeCharactersFromIndex:toIndex:] #2", OFOutOfRangeException,
+	    [s[0] substringFromIndex: 4
+			     toIndex: 4])
+
+	EXPECT_EXCEPTION(@"Detect s > e in "
+	    @"-[removeCharactersFromIndex:toIndex:]",
+	    OFInvalidArgumentException,
+	    [s[0] substringFromIndex: 2
+			     toIndex: 0])
 
 	TEST(@"-[replaceOccurrencesOfString:withString:]",
 	    [[[OFMutableString stringWithString: @"asd fo asd fofo asd"]
 	    replaceOccurrencesOfString: @"fo"
 			    withString: @"foo"]