diff --git a/lib/media/file-utils.js b/lib/media/file-utils.js
--- a/lib/media/file-utils.js
+++ b/lib/media/file-utils.js
@@ -172,6 +172,16 @@
   return replaceExtension(filename, ext);
 }
 
+const basenameRegex = /[^a-z0-9._-]/gi;
+function sanitizeFilename(filename: ?string, mime: string): string {
+  if (!filename) {
+    // Generate a random filename and deduce the extension from the mime type.
+    const randomName = Math.random().toString(36).slice(-5);
+    filename = readableFilename(randomName, mime) || randomName;
+  }
+  return filename.replace(basenameRegex, '_');
+}
+
 const extRegex = /\.([0-9a-z]+)$/i;
 function extensionFromFilename(filename: string): ?string {
   const matches = filename.match(extRegex);
@@ -212,6 +222,7 @@
   fileInfoFromData,
   replaceExtension,
   readableFilename,
+  sanitizeFilename,
   extensionFromFilename,
   pathFromURI,
   filenameFromPathOrURI,
diff --git a/lib/media/video-utils.js b/lib/media/video-utils.js
--- a/lib/media/video-utils.js
+++ b/lib/media/video-utils.js
@@ -4,7 +4,7 @@
 
 import type { Dimensions, MediaMissionFailure } from '../types/media-types';
 import { getUUID } from '../utils/uuid';
-import { replaceExtension } from './file-utils';
+import { replaceExtension, sanitizeFilename } from './file-utils';
 import { maxDimensions } from './media-utils';
 
 const { height: maxHeight, width: maxWidth } = maxDimensions;
@@ -15,7 +15,8 @@
   +inputPath: string,
   +inputHasCorrectContainerAndCodec: boolean,
   +inputFileSize: number, // in bytes
-  +inputFilename: string,
+  +inputFilename: ?string,
+  +inputMimeType: string,
   +inputDuration: number,
   +inputDimensions: Dimensions,
   +outputDirectory: string,
@@ -42,6 +43,7 @@
     inputHasCorrectContainerAndCodec,
     inputFileSize,
     inputFilename,
+    inputMimeType,
     inputDuration,
     inputDimensions,
     outputDirectory,
@@ -62,8 +64,9 @@
   }
 
   const uuid = getUUID();
+  const sanitizedFilename = sanitizeFilename(inputFilename, inputMimeType);
   const thumbnailFilename = replaceExtension(
-    `thumb.${uuid}.${inputFilename}`,
+    `thumb.${uuid}.${sanitizedFilename}`,
     'jpg',
   );
   const thumbnailPath = `${outputDirectory}${thumbnailFilename}`;
@@ -89,7 +92,7 @@
   }
 
   const outputFilename = replaceExtension(
-    `transcode.${uuid}.${inputFilename}`,
+    `transcode.${uuid}.${sanitizedFilename}`,
     'mp4',
   );
   const outputPath = `${outputDirectory}${outputFilename}`;
diff --git a/lib/types/media-types.js b/lib/types/media-types.js
--- a/lib/types/media-types.js
+++ b/lib/types/media-types.js
@@ -213,7 +213,7 @@
   | {
       +step: 'photo_library',
       +dimensions: Dimensions,
-      +filename: string,
+      +filename: ?string,
       +uri: string,
       +mediaNativeID: string,
       +selectTime: number, // ms timestamp
@@ -223,7 +223,7 @@
   | {
       +step: 'video_library',
       +dimensions: Dimensions,
-      +filename: string,
+      +filename: ?string,
       +uri: string,
       +mediaNativeID: string,
       +selectTime: number, // ms timestamp
diff --git a/native/media/media-utils.js b/native/media/media-utils.js
--- a/native/media/media-utils.js
+++ b/native/media/media-utils.js
@@ -3,7 +3,7 @@
 import invariant from 'invariant';
 import { Image } from 'react-native';
 
-import { pathFromURI, readableFilename } from 'lib/media/file-utils';
+import { pathFromURI, sanitizeFilename } from 'lib/media/file-utils';
 import type {
   Dimensions,
   MediaMissionStep,
@@ -89,8 +89,7 @@
     );
     const shouldDisposePath =
       initialURI !== uploadURI ? pathFromURI(uploadURI) : null;
-    const filename = readableFilename(selection.filename, mime);
-    invariant(filename, `could not construct filename for ${mime}`);
+    const filename = sanitizeFilename(selection.filename, mime);
     if (mediaType === 'video') {
       invariant(uploadThumbnailURI, 'video should have uploadThumbnailURI');
       sendResult({
diff --git a/native/media/video-utils.js b/native/media/video-utils.js
--- a/native/media/video-utils.js
+++ b/native/media/video-utils.js
@@ -31,7 +31,7 @@
 type ProcessVideoInfo = {
   +uri: string,
   +mime: string,
-  +filename: string,
+  +filename: ?string,
   +fileSize: number,
   +dimensions: Dimensions,
   +hasWiFi: boolean,
@@ -73,6 +73,7 @@
     inputHasCorrectContainerAndCodec: validFormat,
     inputFileSize: input.fileSize,
     inputFilename: input.filename,
+    inputMimeType: input.mime,
     inputDuration: duration,
     inputDimensions: input.dimensions,
     outputDirectory: temporaryDirectoryPath,