Index: src/OFMutableURI.m
==================================================================
--- src/OFMutableURI.m
+++ src/OFMutableURI.m
@@ -40,10 +40,13 @@
 
 - (void)setScheme: (OFString *)scheme
 {
 	void *pool = objc_autoreleasePoolPush();
 	OFString *old = _percentEncodedScheme;
+
+	if (scheme.length < 1 || !OFASCIIIsAlpha(*scheme.UTF8String))
+		@throw [OFInvalidFormatException exception];
 
 	_percentEncodedScheme = [[scheme.lowercaseString
 	    stringByAddingPercentEncodingWithAllowedCharacters:
 	    [OFCharacterSet URISchemeAllowedCharacterSet]] copy];
 
@@ -55,10 +58,14 @@
 - (void)setPercentEncodedScheme: (OFString *)percentEncodedScheme
 {
 	void *pool = objc_autoreleasePoolPush();
 	OFString *old = _percentEncodedScheme;
 
+	if (percentEncodedScheme.length < 1 ||
+	    !OFASCIIIsAlpha(*percentEncodedScheme.UTF8String))
+		@throw [OFInvalidFormatException exception];
+
 	if (percentEncodedScheme != nil)
 		OFURIVerifyIsEscaped(percentEncodedScheme,
 		    [OFCharacterSet URISchemeAllowedCharacterSet]);
 
 	_percentEncodedScheme = [percentEncodedScheme.lowercaseString copy];

Index: src/OFURI.m
==================================================================
--- src/OFURI.m
+++ src/OFURI.m
@@ -590,11 +590,12 @@
 		void *pool = objc_autoreleasePoolPush();
 		const char *UTF8String = string.UTF8String;
 		size_t length = string.UTF8StringLength;
 		const char *colon;
 
-		if ((colon = strchr(UTF8String, ':')) == NULL)
+		if ((colon = strchr(UTF8String, ':')) == NULL ||
+		    colon - UTF8String < 1 || !OFASCIIIsAlpha(UTF8String[0]))
 			@throw [OFInvalidFormatException exception];
 
 		_percentEncodedScheme = [[[OFString
 		    stringWithUTF8String: UTF8String
 				  length: colon - UTF8String] lowercaseString]