--- a/mobile/android/base/java/org/mozilla/gecko/ChooseBookmarkFolderDialog.java
+++ b/mobile/android/base/java/org/mozilla/gecko/ChooseBookmarkFolderDialog.java
@@ -1,18 +1,21 @@
 /* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 package org.mozilla.gecko;
 
+import android.app.Activity;
+import android.content.Intent;
 import android.os.Bundle;
 import android.support.annotation.Nullable;
 import android.support.annotation.StringRes;
+import android.support.v4.app.FragmentTransaction;
 import android.view.LayoutInflater;
 import android.view.View;
 import android.view.ViewGroup;
 
 public class ChooseBookmarkFolderDialog extends BookmarkFolderTreeDialog {
     private int currentFolderId;
     private String currentFolderName;
 
@@ -47,15 +50,33 @@ public class ChooseBookmarkFolderDialog 
         final View editView = inflater.inflate(R.layout.choose_bookmark_folder, container, false);
 
         setupToolbar(editView, null);
         setupFolderTree(editView, true);
 
         editView.findViewById(R.id.add_new_folder).setOnClickListener(new View.OnClickListener() {
             @Override
             public void onClick(View v) {
-            // TODO: Create new fragment to add a new folder.
+                final CreateBookmarkFolderDialog createFolderDialog = CreateBookmarkFolderDialog.newInstance(currentFolderId, currentFolderName);
+                createFolderDialog.setTargetFragment(ChooseBookmarkFolderDialog.this, TARGET_FRAGMENT_CODE_UNUSED);
+                final FragmentTransaction transaction = getFragmentManager().beginTransaction();
+                transaction.replace(android.R.id.content, createFolderDialog)
+                        .setTransition(FragmentTransaction.TRANSIT_FRAGMENT_OPEN)
+                        .addToBackStack(null)
+                        .commit();
             }
         });
 
         return editView;
     }
+
+    @Override
+    public void onActivityResult(int requestCode, int resultCode, Intent data) {
+        if (resultCode != Activity.RESULT_OK || data == null) {
+            return;
+        }
+
+        // The user just created a new folder - send it straight on to the Edit panel.
+        final String folderName = data.getStringExtra(ARG_FOLDER_NAME);
+        final int folderId = data.getIntExtra(ARG_FOLDER_ID, INVALID_FOLDER_ID);
+        folderSelected(folderName, folderId);
+    }
 }

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/java/org/mozilla/gecko/CreateBookmarkFolderDialog.java
@@ -0,0 +1,116 @@
+/* -*- Mode: Java; c-basic-offset: 4; tab-width: 20; indent-tabs-mode: nil; -*-
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+package org.mozilla.gecko;
+
+import org.mozilla.gecko.db.BrowserDB;
+import org.mozilla.gecko.util.ThreadUtils;
+import org.mozilla.gecko.util.UIAsyncTask;
+
+import android.content.ContentResolver;
+import android.os.Bundle;
+import android.support.annotation.Nullable;
+import android.support.annotation.StringRes;
+import android.support.design.widget.Snackbar;
+import android.support.design.widget.TextInputLayout;
+import android.view.LayoutInflater;
+import android.view.View;
+import android.view.ViewGroup;
+import android.widget.EditText;
+
+public class CreateBookmarkFolderDialog extends BookmarkToolbarDialog {
+    // The id and name of the folder in which the new folder will be created.
+    private int parentFolderId;
+    private String parentFolderName;
+
+    private ViewGroup rootView;
+    private EditText newFolderNameEdit;
+
+    public static CreateBookmarkFolderDialog newInstance(int currentFolderId, String currentFolderName) {
+        final CreateBookmarkFolderDialog dialog = new CreateBookmarkFolderDialog();
+        dialog.setDialogFolderArguments(currentFolderId, currentFolderName);
+        return dialog;
+    }
+
+    @Override
+    public void onCreate(@Nullable Bundle savedInstanceState) {
+        super.onCreate(savedInstanceState);
+
+        final Bundle args = getArguments();
+        parentFolderId = args.getInt(ARG_FOLDER_ID);
+        parentFolderName = args.getString(ARG_FOLDER_NAME);
+    }
+
+    @Override
+    protected @StringRes int toolbarTitle() {
+        return R.string.bookmark_dialog_add_folder_title;
+    }
+
+    private void toolbarSaveClicked() {
+        final String newFolderName = newFolderNameEdit.getText().toString().trim();
+        if (newFolderName.isEmpty()) {
+            newFolderNameEdit.requestFocus();
+            // The name edit starts out blank, and the text watcher doesn't run until text is
+            // entered, so just in case that's the state we're in, enter some empty text to trigger
+            // the text watcher error.
+            newFolderNameEdit.setText("");
+            return;
+        }
+
+        final BrowserDB db = BrowserDB.from(getContext());
+        (new UIAsyncTask.WithoutParams<Long>(ThreadUtils.getBackgroundHandler()) {
+            @Override
+            public Long doInBackground() {
+                final ContentResolver cr = getContext().getContentResolver();
+                db.addBookmarkFolder(cr, newFolderName, parentFolderId);
+                return db.getIDForFolder(cr, newFolderName, parentFolderId);
+            }
+
+            @Override
+            public void onPostExecute(Long newFolderId) {
+                if (newFolderId == null) {
+                    return;
+                }
+
+                Snackbar.make(rootView, R.string.bookmark_folder_created, Snackbar.LENGTH_SHORT).show();
+                folderSelected(newFolderName, newFolderId.intValue());
+            }
+        }).execute();
+    }
+
+    @Override
+    protected boolean toolbarMenuItemClicked(int menuItemId) {
+        if (menuItemId == R.id.save) {
+            toolbarSaveClicked();
+            return true;
+        }
+        return false;
+    }
+
+    @Nullable
+    @Override
+    public View onCreateView(LayoutInflater inflater, final ViewGroup container, Bundle savedInstanceState) {
+        final View folderCreateView = inflater.inflate(R.layout.create_bookmark_folder, container, false);
+        rootView = container;
+
+        setupToolbar(folderCreateView, R.menu.bookmarks_dialog_menu_save);
+
+        final TextInputLayout newFolderNameLayout = (TextInputLayout) folderCreateView.findViewById(R.id.new_folder_name_layout);
+        newFolderNameEdit = (EditText) folderCreateView.findViewById(R.id.new_folder_name);
+        final String emptyFolderNameErrorText = getString(R.string.bookmark_add_folder_name_empty_error);
+        newFolderNameEdit.addTextChangedListener(new EmptyTextWatcher(newFolderNameLayout, emptyFolderNameErrorText));
+
+        final EditText selectParentFolderEdit = (EditText) folderCreateView.findViewById(R.id.select_parent_folder);
+        selectParentFolderEdit.setText(parentFolderName);
+        selectParentFolderEdit.setOnClickListener(new View.OnClickListener() {
+            @Override
+            public void onClick(View v) {
+                // TODO: Create new fragment to select the parent folder of the new folder.
+            }
+        });
+
+        return folderCreateView;
+    }
+}

--- a/mobile/android/base/locales/en-US/android_strings.dtd
+++ b/mobile/android/base/locales/en-US/android_strings.dtd
@@ -69,16 +69,17 @@
 <!ENTITY bookmark_remove "Remove bookmark">
 <!ENTITY bookmark_added "Bookmark added">
 <!-- Localization note (bookmark_already_added) : This string is
      used as a label in a toast. It is the verb "to bookmark", not
      the noun "a bookmark". -->
 <!ENTITY bookmark_already_added "Already bookmarked">
 <!ENTITY bookmark_removed "Bookmark removed">
 <!ENTITY bookmark_updated "Bookmark updated">
+<!ENTITY bookmark_folder_created "Folder created">
 <!ENTITY bookmark_options "Options">
 <!-- Localization note (selected_folder): Alternate text for accessibility; not UI visible.
      Indicates which Bookmarks folder is currently selected (selected is an adjective and not a verb
      here). -->
 <!ENTITY bookmarks_selected_folder "Selected folder">
 <!ENTITY screenshot_added_to_bookmarks "Screenshot added to bookmarks">
 <!-- Localization note (screenshot_folder_label_in_bookmarks): We save links to screenshots
      the user takes. The folder we store these links in is located in the bookmarks list
@@ -94,16 +95,21 @@
 <!ENTITY bookmark_dialog_new_folder "New folder...">
 
 <!ENTITY bookmark_edit_title "Edit Bookmark">
 <!ENTITY bookmark_edit_name "Name">
 <!ENTITY bookmark_edit_location "Location">
 <!ENTITY bookmark_edit_keyword "Keyword">
 <!ENTITY bookmark_edit_location_empty_error "Bookmark location must contain a URL">
 
+<!ENTITY bookmark_dialog_add_folder_title "Add folder">
+<!ENTITY bookmark_add_folder_name_empty_error "Folder name is required">
+<!ENTITY bookmark_add_folder_title "Title">
+<!ENTITY bookmark_add_folder_parent_folder "Parent folder">
+
 <!-- Localization note (bookmark_folder_items): The variable is replaced by the number of items
      in the folder. -->
 <!ENTITY bookmark_folder_items "&formatD; items">
 <!ENTITY bookmark_folder_one_item "1 item">
 
 <!ENTITY reader_saved_offline "Saved offline">
 <!-- Localization note (reader_switch_to_bookmarks) : This
      string is used as an action in a snackbar - it lets you

--- a/mobile/android/base/moz.build
+++ b/mobile/android/base/moz.build
@@ -345,16 +345,17 @@ gbjar.sources += ['java/org/mozilla/geck
     'BookmarkFolderTreeDialog.java',
     'BookmarkToolbarDialog.java',
     'BootReceiver.java',
     'BrowserApp.java',
     'BrowserLocaleManager.java',
     'ChooseBookmarkFolderDialog.java',
     'cleanup/FileCleanupController.java',
     'cleanup/FileCleanupService.java',
+    'CreateBookmarkFolderDialog.java',
     'CustomEditText.java',
     'customtabs/CustomTabsActivity.java',
     'customtabs/GeckoCustomTabsService.java',
     'DataReportingNotification.java',
     'db/AbstractPerProfileDatabaseProvider.java',
     'db/AbstractTransactionalProvider.java',
     'db/BaseTable.java',
     'db/BrowserDatabaseHelper.java',

new file mode 100644
--- /dev/null
+++ b/mobile/android/base/resources/layout/create_bookmark_folder.xml
@@ -0,0 +1,63 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- This Source Code Form is subject to the terms of the Mozilla Public
+   - License, v. 2.0. If a copy of the MPL was not distributed with this
+   - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
+
+<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
+              xmlns:app="http://schemas.android.com/apk/res-auto"
+              android:orientation="vertical"
+              android:layout_width="match_parent"
+              android:layout_height="match_parent"
+              android:background="@android:color/white"
+              android:theme="@style/GeckoAlertDialog">
+
+    <include layout="@layout/bookmark_dialog_toolbar"/>
+
+    <ScrollView android:layout_width="match_parent"
+                android:layout_height="match_parent"
+                android:layout_gravity="center_horizontal">
+
+        <LinearLayout android:layout_width="match_parent"
+                      android:layout_height="wrap_content"
+                      android:padding="24dp"
+                      android:orientation="vertical">
+
+            <android.support.design.widget.TextInputLayout
+                    android:layout_width="match_parent"
+                    android:layout_height="wrap_content"
+                    android:id="@+id/new_folder_name_layout"
+                    app:hintAnimationEnabled="true">
+
+                <android.support.design.widget.TextInputEditText
+                        android:id="@+id/new_folder_name"
+                        android:layout_width="match_parent"
+                        android:layout_height="wrap_content"
+                        android:maxLines="1"
+                        android:hint="@string/bookmark_add_folder_title">
+                    <requestFocus/>
+                </android.support.design.widget.TextInputEditText>
+            </android.support.design.widget.TextInputLayout>
+
+            <android.support.design.widget.TextInputLayout
+                    android:layout_width="match_parent"
+                    android:layout_height="wrap_content"
+                    app:hintAnimationEnabled="true">
+
+                <!-- Use focusableInTouchMode="false" so that the text edit receives a click event
+                     the first time it's clicked - otherwise the first tap only focuses the field
+                     and you don't get a click event until the second tap. -->
+                <android.support.design.widget.TextInputEditText
+                        android:id="@+id/select_parent_folder"
+                        android:layout_width="match_parent"
+                        android:layout_height="wrap_content"
+                        android:maxLines="1"
+                        android:focusableInTouchMode="false"
+                        android:hint="@string/bookmark_add_folder_parent_folder"
+                        android:editable="false"/>
+            </android.support.design.widget.TextInputLayout>
+
+        </LinearLayout>
+
+    </ScrollView>
+
+</LinearLayout>

--- a/mobile/android/base/strings.xml.in
+++ b/mobile/android/base/strings.xml.in
@@ -91,16 +91,17 @@
 
   <string name="quit">&quit;</string>
   <string name="bookmark">&bookmark;</string>
   <string name="bookmark_remove">&bookmark_remove;</string>
   <string name="bookmark_added">&bookmark_added;</string>
   <string name="bookmark_already_added">&bookmark_already_added;</string>
   <string name="bookmark_removed">&bookmark_removed;</string>
   <string name="bookmark_updated">&bookmark_updated;</string>
+  <string name="bookmark_folder_created">&bookmark_folder_created;</string>
   <string name="bookmark_options">&bookmark_options;</string>
   <string name="bookmarks_selected_folder">&bookmarks_selected_folder;</string>
   <string name="screenshot_added_to_bookmarks">&screenshot_added_to_bookmarks;</string>
   <string name="screenshot_folder_label_in_bookmarks">&screenshot_folder_label_in_bookmarks;</string>
   <string name="readinglist_smartfolder_label_in_bookmarks">&readinglist_smartfolder_label_in_bookmarks;</string>
 
   <string name="bookmark_dialog_save_and_return">&bookmark_dialog_save_and_return;</string>
   <string name="bookmark_dialog_folder">&bookmark_dialog_folder;</string>
@@ -108,16 +109,21 @@
   <string name="bookmark_dialog_new_folder">&bookmark_dialog_new_folder;</string>
 
   <string name="bookmark_edit_title">&bookmark_edit_title;</string>
   <string name="bookmark_edit_name">&bookmark_edit_name;</string>
   <string name="bookmark_edit_location">&bookmark_edit_location;</string>
   <string name="bookmark_edit_keyword">&bookmark_edit_keyword;</string>
   <string name="bookmark_edit_location_empty_error">&bookmark_edit_location_empty_error;</string>
 
+  <string name="bookmark_dialog_add_folder_title">&bookmark_dialog_add_folder_title;</string>
+  <string name="bookmark_add_folder_name_empty_error">&bookmark_add_folder_name_empty_error;</string>
+  <string name="bookmark_add_folder_title">&bookmark_add_folder_title;</string>
+  <string name="bookmark_add_folder_parent_folder">&bookmark_add_folder_parent_folder;</string>
+
   <string name="bookmark_folder_items">&bookmark_folder_items;</string>
   <string name="bookmark_folder_one_item">&bookmark_folder_one_item;</string>
 
   <string name="reader_saved_offline">&reader_saved_offline;</string>
   <string name="reader_switch_to_bookmarks">&reader_switch_to_bookmarks;</string>
 
   <string name="history_today_section">&history_today_section;</string>
   <string name="history_yesterday_section">&history_yesterday_section;</string>