diff --git a/pagure/default_config.py b/pagure/default_config.py
index 2aed1c3..7fb7cfd 100644
--- a/pagure/default_config.py
+++ b/pagure/default_config.py
@@ -232,3 +232,7 @@ PAGURE_CI_SERVICES = []
 
 # Boolean to turn on project being by default in the user's namespace
 USER_NAMESPACE = False
+
+# list of allowed tag colors
+TAG_COLOR_LIST = ['DeepSkyBlue', 'red', 'maroon', 'SlateBlue', 'teal', 'green',
+                  'brown', 'orange', 'gray', 'purple', 'black']
diff --git a/pagure/forms.py b/pagure/forms.py
index e5daf63..1283802 100644
--- a/pagure/forms.py
+++ b/pagure/forms.py
@@ -226,7 +226,7 @@ class RemoteRequestPullForm(RequestPullForm):
 
 
 class AddIssueTagForm(PagureForm):
-    ''' Form to add a comment to an issue. '''
+    ''' Form to add a tag to an issue. '''
     tag = wtforms.TextField(
         'tag',
         [
@@ -235,6 +235,18 @@ class AddIssueTagForm(PagureForm):
             wtforms.validators.Length(max=255),
         ]
     )
+    tag_color = wtforms.SelectField(
+        'tag_color',
+        [wtforms.validators.Optional()],
+        choices=[]
+    )
+
+    def __init__(self, *args, **kwargs):
+        super(AddIssueTagForm, self).__init__(*args, **kwargs)
+        self.tag_color.choices = [
+            (tag_color, tag_color) for tag_color in
+                pagure.APP.config['TAG_COLOR_LIST']
+        ]
 
 
 class StatusForm(PagureForm):
@@ -287,7 +299,6 @@ class NewTokenForm(PagureForm):
             ]
 
 
-
 class UpdateIssueForm(PagureForm):
     ''' Form to add a comment to an issue. '''
     tag = wtforms.TextField(
diff --git a/pagure/lib/__init__.py b/pagure/lib/__init__.py
index 8de7e57..3498a2f 100644
--- a/pagure/lib/__init__.py
+++ b/pagure/lib/__init__.py
@@ -331,9 +331,21 @@ def add_tag_obj(session, obj, tags, user, ticketfolder):
         if known:
             continue
 
-        tagobj = get_tag(session, objtag)
+        if isinstance(obj, model.Project):
+            proj_id = obj.id
+        else:
+            proj_id = obj.project.id
+        tagobj = get_tag(session, objtag, proj_id)
         if not tagobj:
-            tagobj = model.Tag(tag=objtag)
+            if isinstance(obj, model.Project):
+                project_id = obj.id
+            else:
+                project_id = obj.project.id
+
+            tagobj = model.Tag(tag=objtag,
+                               tag_color="DeepSkyBlue",
+                               project_id=project_id)
+
             session.add(tagobj)
             session.flush()
 
@@ -341,6 +353,8 @@ def add_tag_obj(session, obj, tags, user, ticketfolder):
             dbobjtag = model.TagIssue(
                 issue_uid=obj.uid,
                 tag=tagobj.tag,
+                tag_color=tagobj.tag_color,
+                tag_id=tagobj.tag_id
             )
         if isinstance(obj, model.Project):
             dbobjtag = model.TagProject(
@@ -641,17 +655,27 @@ def remove_tags(session, project, tags, ticketfolder, user):
 
     msgs = []
     removed_tags = []
-    if not issues:
+    tag_found = False
+    for tag in tags:
+        deltags = session.query(model.Tag).filter(
+            model.Tag.tag == tag).filter(
+            model.Tag.project_id == project.id).all()
+        for deltag in deltags:
+            tag_found = True
+            removed_tags.append(tag)
+            msgs.append('Removed tag: %s' % tag)
+            session.delete(deltag)
+
+    if not tag_found:
         raise pagure.exceptions.PagureException(
-            'No issue found with the tags: %s' % ', '.join(tags))
-    else:
+            'Tags not found: %s' % ', '.join(tags))
+
+    if issues is not None:
         for issue in issues:
             for issue_tag in issue.tags:
                 if issue_tag.tag in tags:
                     tag = issue_tag.tag
-                    removed_tags.append(tag)
                     session.delete(issue_tag)
-                    msgs.append('Removed tag: %s' % tag)
             pagure.lib.git.update_git(
                 issue, repo=issue.project, repofolder=ticketfolder)
 
@@ -669,8 +693,7 @@ def remove_tags(session, project, tags, ticketfolder, user):
     return msgs
 
 
-def remove_tags_obj(
-        session, obj, tags, ticketfolder, user):
+def remove_tags_obj(session, obj, tags, ticketfolder, user):
     ''' Removes the specified tag(s) of a given object. '''
     user_obj = get_user(session, user)
 
@@ -708,68 +731,89 @@ def remove_tags_obj(
     return 'Removed tag: %s' % ', '.join(removed_tags)
 
 
-def edit_issue_tags(session, project, old_tag, new_tag, ticketfolder, user):
+def edit_issue_tags(session, project, old_tag, new_tag, old_tag_color,
+                    new_tag_color, ticketfolder, user):
     ''' Removes the specified tag of a project. '''
     user_obj = get_user(session, user)
 
-    if old_tag == new_tag:
+    if old_tag == new_tag and old_tag_color == new_tag_color:
+        # check for change
         raise pagure.exceptions.PagureException(
-            'Old tag: "%s" is the same as new tag "%s", nothing to change'
-            % (old_tag, new_tag))
+            'No change.  Old tag "%s(%s)" is the same as new tag "%s(%s)"'
+            % (old_tag, old_tag_color, new_tag, new_tag_color))
+    elif old_tag != new_tag:
+        # Check if new tag already exists
+        existing_tag = session.query(model.Tag).filter(
+            model.Tag.tag == new_tag).filter(
+            model.Tag.project_id == project.id).all()
+        if existing_tag is not None and len(existing_tag) > 0:
+            raise pagure.exceptions.PagureException(
+                'Can not rename a tag to an existing tag name: ' + new_tag)
 
     issues = search_issues(session, project, closed=False, tags=old_tag)
     issues.extend(search_issues(session, project, closed=True, tags=old_tag))
 
-    msgs = []
-    if not issues:
-        raise pagure.exceptions.PagureException(
-            'No issue found with the tags: %s' % old_tag)
-    else:
-        tagobj = get_tag(session, new_tag)
-        if not tagobj:
-            tagobj = model.Tag(tag=new_tag)
-            session.add(tagobj)
-            session.flush()
+    # Grab the old tag (there can only be one), and remove it.
+    orig_tags = session.query(model.Tag).filter(
+        model.Tag.tag == old_tag).filter(
+            model.Tag.project_id == project.id).all()
+
+    if orig_tags is not None and len(orig_tags) > 0:
+        session.delete(orig_tags[0])
+        session.commit()
 
+        # Now, add the new tag since the old was removed
+        tagobj = model.Tag(tag=new_tag, tag_color=new_tag_color,
+                           project_id=project.id)
+        session.add(tagobj)
+        session.flush()
+
+        # Update the Issues tag list
         for issue in set(issues):
-            add = True
-            # Drop the old tag
+            # Drop the old tag from the issue
             cnt = 0
             while cnt < len(issue.tags):
                 issue_tag = issue.tags[cnt]
                 if issue_tag.tag == old_tag:
                     issue.tags.remove(issue_tag)
                     cnt -= 1
-                if issue_tag.tag == new_tag:
-                    add = False
                 cnt += 1
             session.flush()
 
-            # Add the new one
-            if add:
-                issue_tag = model.TagIssue(
-                    issue_uid=issue.uid,
-                    tag=tagobj.tag
-                )
-                session.add(issue_tag)
-                session.flush()
+            # Add the new one to the issue
+            issue_tag = model.TagIssue(
+                issue_uid=issue.uid,
+                tag=tagobj.tag,
+                tag_color=tagobj.tag_color,
+                tag_id=tagobj.tag_id
+            )
+            issue.tags.append(issue_tag)
+            session.add(issue_tag)
+            session.flush()
 
             # Update the git version
             pagure.lib.git.update_git(
                 issue, repo=issue.project, repofolder=ticketfolder)
+    else:
+        raise pagure.exceptions.PagureException(
+            'Tag not found: %s' % old_tag)
 
-        msgs.append('Edited tag: %s to %s' % (old_tag, new_tag))
-        pagure.lib.notify.log(
-            project,
-            topic='project.tag.edited',
-            msg=dict(
-                project=project.to_json(public=True),
-                old_tag=old_tag,
-                new_tag=new_tag,
-                agent=user_obj.username,
-            ),
-            redis=REDIS,
-        )
+    msgs = []
+    msgs.append('Edited tag: %s(%s) to %s(%s)' %
+                (old_tag, old_tag_color, new_tag, new_tag_color))
+    pagure.lib.notify.log(
+        project,
+        topic='project.tag.edited',
+        msg=dict(
+            project=project.to_json(public=True),
+            old_tag=old_tag,
+            old_tag_color=old_tag_color,
+            new_tag=new_tag,
+            new_tag_color=new_tag_color,
+            agent=user_obj.username,
+        ),
+        redis=REDIS,
+    )
 
     return msgs
 
@@ -1338,6 +1382,11 @@ def new_pull_request(session, branch_from,
     return request
 
 
+def new_tag(tag_name, tag_color, project_id):
+    ''' Return a new tag object '''
+    return model.Tag(tag=tag_name, tag_color=tag_color, project_id=project_id)
+
+
 def edit_issue(session, issue, ticketfolder, user,
                title=None, content=None, status=None, close_status=None,
                priority=None, milestone=None, private=False):
@@ -2021,11 +2070,9 @@ def get_tags_of_project(session, project, pattern=None):
     query = session.query(
         model.Tag
     ).filter(
-        model.Tag.tag == model.TagIssue.tag
+        model.Tag.tag != ""
     ).filter(
-        model.TagIssue.issue_uid == model.Issue.uid
-    ).filter(
-        model.Issue.project_id == project.id
+        model.Tag.project_id == project.id
     ).order_by(
         model.Tag.tag
     )
@@ -2038,13 +2085,15 @@ def get_tags_of_project(session, project, pattern=None):
     return query.all()
 
 
-def get_tag(session, tag):
+def get_tag(session, tag, project_id):
     ''' Returns a Tag object for the given tag text.
     '''
     query = session.query(
         model.Tag
     ).filter(
         model.Tag.tag == tag
+    ).filter(
+        model.Tag.project_id == project_id
     )
 
     return query.first()
diff --git a/pagure/lib/model.py b/pagure/lib/model.py
index c44b604..1aaf1b6 100644
--- a/pagure/lib/model.py
+++ b/pagure/lib/model.py
@@ -1034,9 +1034,18 @@ class Tag(BASE):
 
     __tablename__ = 'tags'
 
-    tag = sa.Column(sa.String(255), primary_key=True)
+    tag_id = sa.Column(sa.Integer, primary_key=True)
+    tag = sa.Column(sa.String(255), nullable=False)
+    tag_color = sa.Column(sa.String(25), default="DeepSkyBlue")
     date_created = sa.Column(sa.DateTime, nullable=False,
                              default=datetime.datetime.utcnow)
+    project_id = sa.Column(sa.Integer, nullable=False)
+
+    def __init__(self, tag=None, project_id=None, tag_color="DeepSkyBlue"):
+        # Create our unique tag identifier
+        self.tag = tag
+        self.project_id = project_id
+        self.tag_color = tag_color
 
 
 class TagIssue(BASE):
@@ -1047,10 +1056,10 @@ class TagIssue(BASE):
 
     __tablename__ = 'tags_issues'
 
-    tag = sa.Column(
-        sa.String(255),
+    tag_id = sa.Column(
+        sa.Integer,
         sa.ForeignKey(
-            'tags.tag', ondelete='CASCADE', onupdate='CASCADE',
+            'tags.tag_id', ondelete='CASCADE', onupdate='CASCADE',
         ),
         primary_key=True)
     issue_uid = sa.Column(
@@ -1059,6 +1068,16 @@ class TagIssue(BASE):
             'issues.uid', ondelete='CASCADE', onupdate='CASCADE',
         ),
         primary_key=True)
+    tag_color = sa.Column(
+        sa.String(25),
+        sa.ForeignKey(
+            'tags.tag_color', ondelete='CASCADE', onupdate='CASCADE',
+        ))
+    tag = sa.Column(
+        sa.String(255),
+        sa.ForeignKey(
+            'tags.tag', ondelete='CASCADE', onupdate='CASCADE',
+        ))
     date_created = sa.Column(sa.DateTime, nullable=False,
                              default=datetime.datetime.utcnow)
 
diff --git a/pagure/templates/edit_tag.html b/pagure/templates/edit_tag.html
index 254fbcf..0cc503a 100644
--- a/pagure/templates/edit_tag.html
+++ b/pagure/templates/edit_tag.html
@@ -8,25 +8,41 @@
 
 {% block repo %}
 
-<h2>Edit tag: {{ edit_tag }}</h2>
-
 <section class="edit_tag">
-    <form action="{{ url_for('.edit_tag',
-                    repo=repo.name,
-                    username=username,
-                    namespace=repo.namespace,
-                    tag=edit_tag) }}" method="post">
-
-    <p>Enter in the field below the new name for the tag: "{{ edit_tag }}"</p>
-    <table>
-      {{ render_field_in_row(form.tag) }}
-    </table>
-    <p class="buttons indent">
-      <input type="submit" class="submit positive button" value="Edit">
-      <input type="button" value="Cancel" class="button" onclick="history.back();">
-      {{ form.csrf_token }}
-    </p>
-  </form>
+    <div class="col-md-8 col-md-offset-2">
+      <div class="card">
+        <div class="card-header">
+          <strong>Edit tag: {{ edit_tag }}</strong>
+        </div>
+        <form action="{{ url_for(
+              '.edit_tag',
+              tag=edit_tag,
+              repo=repo.name,
+              username=username,
+              namespace=repo.namespace) }}"
+            method="post" class="icon">
+            {{ form.csrf_token }}
+          <div class="row p-t-1">
+          <div class="col-sm-6 p-r-0">
+            <input type="text" name=tag
+              value={{ edit_tag }} size="3" class="form-control"/>
+          </div>
+          <div class="col-sm-2 p-r-0">
+            <select id="tag_color" name="tag_color" style="background-color:{{tag_color}}; width: 80px;" class="c-select"
+              onChange="this.style.backgroundColor=this.options[this.selectedIndex].style.backgroundColor">
+              {% for color_opt in color_list %}
+                <option value={{ color_opt }} style="background-color:{{color_opt}}" {% if tag_color == color_opt %}selected{% endif %}></option>
+              {% endfor %}
+            </select>
+          </div>
+        </div>
+          <p class="buttons indent">
+            <input type="submit" class="submit positive button" value="Update Tag">
+            <input type="button" value="Cancel" class="button" onclick="history.back();">
+            {{ form.csrf_token }}
+          </p>
+        </form>
+      </div>
+    </div>
 </section>
-
 {% endblock %}
diff --git a/pagure/templates/issue.html b/pagure/templates/issue.html
index ca1f4cf..4e5a186 100644
--- a/pagure/templates/issue.html
+++ b/pagure/templates/issue.html
@@ -159,7 +159,7 @@
             <label><strong>Tags</strong></label>
               <h4 id="taglist">
                 {% for tag in issue.tags %}
-                  <a id="tag-{{ tag.tag }}" class="label label-default"
+                  <a id="tag-{{ tag.tag }}" style="background-color:{{ tag.tag_color}}" class="label label-default"
                     href="{{ url_for('view_issues',
                         repo=repo.name,
                         username=username,
@@ -890,7 +890,7 @@ $( document ).ready(function() {
     delimiter: ',',
     options: items,
     persist: false,
-    create: true,
+    create: false,
     labelField: "item",
     valueField: "item",
   });
diff --git a/pagure/templates/issues.html b/pagure/templates/issues.html
index 0d358bc..d609b3c 100644
--- a/pagure/templates/issues.html
+++ b/pagure/templates/issues.html
@@ -143,7 +143,7 @@
                     repo=repo.name ) }}" method="GET">
         <div class="input-group">
           <input type="hidden" name="status" value="{{ status }}" />
-          {% for tag in tags %}
+          {% for tag in tag_list %}
           <input type="hidden" name="tags" value="{{ tag }}" />
           {% endfor %}
            <input type="text" class="form-control input-sm"
@@ -230,8 +230,8 @@
                   {{issue.user_comments|count}}
             </span>
               {% endif %}
-              {% for tag in issue.tags%}
-                <span class="label label-info">{{tag.tag}}</span>
+              {% for tag in issue.tags %}
+                <span class="label label-info" style="background-color:{{tag.tag_color}}">{{tag.tag}}</span>
               {% endfor%}
             </td>
             <td class="td-open_date nowrap">
diff --git a/pagure/templates/settings.html b/pagure/templates/settings.html
index 5a9fd5a..96a1924 100644
--- a/pagure/templates/settings.html
+++ b/pagure/templates/settings.html
@@ -750,8 +750,7 @@
         </div>
         <div class="card-block">
           <p>
-            Here below is the list of tags associated with one or more issue of
-            the project.
+            Here is the list of tags associated with this project.
           </p>
         </div>
         <ul class="list-group list-group-flush">
@@ -765,6 +764,7 @@
                 tags=tag.tag) }}">
               <span class="oi" data-glyph="tag"></span>&nbsp; {{ tag.tag }}
             </a>
+            &nbsp<span class="label label-info" style="background-color:{{tag.tag_color}}">{{tag.tag}}</span>
             <div class="pull-xs-right">
             <form class="icon del_icon pull-xs-right" method="POST"
               action="{{ url_for(
@@ -785,7 +785,8 @@
                   repo=repo.name,
                   username=username,
                   namespace=repo.namespace,
-                  tag=tag.tag) }}">
+                  tag=tag.tag,
+                  tag_color=tag.tag_color) }}">
               <button class="btn btn-default btn-sm" title="Edit tag">
                 <span class="oi" data-glyph="pencil"></span>
               </button>
@@ -794,6 +795,34 @@
           </li>
         {% endfor %}
         </ul>
+        <form action="{{ url_for(
+              '.update_tags',
+              repo=repo.name,
+              username=username,
+              namespace=repo.namespace) }}"
+            method="post" class="icon">
+          {{ tag_form.csrf_token }}
+          <div class="card-block">
+          <!-- The "Add New Tag" rows/elements will fill in here  -->
+          <div id="tagcolor">
+          </div>
+          <div class="row p-t-1">
+            <div class="col-sm-6">
+              <a class="btn btn-secondary btn-sm btn-block" id="new_tag">
+                  Add New Tag
+              </a>
+            </div>
+          </div>
+          <div class="row p-t-1">
+            <div class="col-sm-12">
+              <button class="btn btn-primary" type="submit"
+                  title="Update the tags">
+                Update
+              </button>
+            </div>
+          </div>
+        </div>
+        </form>
       </div>
     </div>
     {% endif %}
@@ -966,6 +995,42 @@ $('#default_close_status').click(function(e) {
 });
 {% endif %}
 
+
+var first_new_tag = 1;
+$('#new_tag').click(function(e) {
+  console.log('new tag');
+  console.log($('#tagcolor'));
+  if (first_new_tag == 1){
+    // Only display the Tag row the first time Add New Tag is clicked
+    $('#tagcolor').append(
+     '<div class="row">\
+        <div class="col-sm-6">\
+          <strong>New Tag</strong>\
+        </div>\
+        <div class="col-sm-6">\
+          <strong>Tag Color</strong>\
+        </div>\
+      </div>');
+    first_new_tag = 0;
+  }
+  $('#tagcolor').append(
+   '<div class="row p-t-1"> \
+        <div class="col-sm-6 p-r-0">\
+          <input type="text" name="tag"\
+            value="" size="3" class="form-control"/>\
+        </div>\
+        <div class="col-sm-6 p-r-0">\
+          <select id="tag_color_select" name="tag_color_select" style="background-color:DeepSkyBlue; width: 80px;"\
+            onChange="this.style.backgroundColor=this.options[this.selectedIndex].style.backgroundColor">\
+            {% for color_opt in color_list %}\
+              <option value={{ color_opt }} style="background-color:{{color_opt}}"></option>\
+            {% endfor %}\
+          </select>\
+        </div>\
+    </div>'
+  );
+});
+
 $('.extend-form').click(function(e) {
   const tgt = $(this).attr('data-target');
   let form = $(tgt + ' > div:last-child').clone();
diff --git a/pagure/ui/issues.py b/pagure/ui/issues.py
index 537c968..c931ed5 100644
--- a/pagure/ui/issues.py
+++ b/pagure/ui/issues.py
@@ -374,16 +374,25 @@ def edit_tag(repo, tag, username=None, namespace=None):
         flask.abort(404, 'No issue tracker found for this project')
 
     tags = pagure.lib.get_tags_of_project(SESSION, repo)
-
-    if not tags or tag not in [t.tag for t in tags]:
+    if not tags:
+        flask.abort(404, 'Project has no tags to edit')
+
+    # Check the tag exists, and get its old/original color
+    found = False
+    for t in tags:
+        if t.tag == tag:
+            old_tag_color = t.tag_color
+            found = True
+            break
+    if not found:
         flask.abort(404, 'Tag %s not found in this project' % tag)
 
     form = pagure.forms.AddIssueTagForm()
     if form.validate_on_submit():
         new_tag = form.tag.data
-
+        new_tag_color = form.tag_color.data
         msgs = pagure.lib.edit_issue_tags(
-            SESSION, repo, tag, new_tag,
+            SESSION, repo, tag, new_tag, old_tag_color, new_tag_color,
             user=flask.g.fas_user.username,
             ticketfolder=APP.config['TICKETS_FOLDER']
         )
@@ -407,9 +416,76 @@ def edit_tag(repo, tag, username=None, namespace=None):
         username=username,
         repo=repo,
         edit_tag=tag,
+        tag_color=old_tag_color,
+        color_list=pagure.APP.config['TAG_COLOR_LIST']
     )
 
 
+@APP.route('/<repo>/update/tags', methods=['POST'])
+@APP.route('/<namespace>/<repo>/update/tags', methods=['POST'])
+@login_required
+def update_tags(repo, username=None, namespace=None):
+    """ Update the tags of a project.
+    """
+
+    repo = flask.g.repo
+
+    if not repo.settings.get('issue_tracker', True):
+        flask.abort(404, 'No issue tracker found for this project')
+
+    if not flask.g.repo_admin:
+        flask.abort(
+            403,
+            'You are not allowed to change the settings for this project')
+
+    form = pagure.forms.ConfirmationForm()
+
+    error = False
+    if form.validate_on_submit():
+        tag_names = flask.request.form.getlist('tag')
+        tag_colors = flask.request.form.getlist('tag_color_select')
+
+        tags = []
+        colors = []
+        for t in range(len(tag_names)):
+            if tag_names[t] == "":
+                # Blank field, ignore
+                continue
+            tags.append(tag_names[t].strip())
+            colors.append(tag_colors[t].strip())
+
+        if len(tags) != len(colors):
+            flask.flash(
+                'tags and tag colors are not of the same length', 'error')
+            error = True
+
+        for tag in tags:
+            if tag.strip() and tags.count(tag) != 1:
+                flask.flash(
+                    'Tag %s is present %s times' % (
+                        tag, tags.count(tag)
+                    ),
+                    'error')
+                error = True
+                break
+
+        if not error:
+            for cnt in range(len(tags)):
+                new_tag = pagure.lib.new_tag(tags[cnt].strip(),
+                                             colors[cnt], repo.id)
+                try:
+                    SESSION.add(new_tag)
+                    SESSION.commit()
+                    flask.flash('Tags updated')
+                except SQLAlchemyError as err:  # pragma: no cover
+                    SESSION.rollback()
+                    flask.flash(str(err), 'error')
+
+    return flask.redirect(flask.url_for(
+        'view_settings', username=username, repo=repo.name,
+        namespace=namespace))
+
+
 @APP.route('/<repo>/droptag/', methods=['POST'])
 @APP.route('/<namespace>/<repo>/droptag/', methods=['POST'])
 @APP.route('/fork/<username>/<repo>/droptag/', methods=['POST'])
diff --git a/pagure/ui/repo.py b/pagure/ui/repo.py
index 60d354c..9e80472 100644
--- a/pagure/ui/repo.py
+++ b/pagure/ui/repo.py
@@ -1080,6 +1080,7 @@ def view_settings(repo, username=None, namespace=None):
         tags=tags,
         plugins=plugins,
         branchname=branchname,
+        color_list=pagure.APP.config['TAG_COLOR_LIST']
     )
 
 
diff --git a/tests/test_pagure_flask_api.py b/tests/test_pagure_flask_api.py
index 44fffca..cc2269b 100644
--- a/tests/test_pagure_flask_api.py
+++ b/tests/test_pagure_flask_api.py
@@ -77,13 +77,14 @@ class PagureFlaskApitests(tests.Modeltests):
         self.session.add(item)
         self.session.commit()
         item = pagure.lib.model.Tag(
-            tag='tag1',
+            tag='tag1', tag_color='DeepBlueSky', project_id=1,
         )
         self.session.add(item)
         self.session.commit()
         item = pagure.lib.model.TagIssue(
             tag='tag1',
             issue_uid='foobar',
+            tag_id=tag.tag_id
         )
         self.session.add(item)
         self.session.commit()
diff --git a/tests/test_pagure_flask_ui_issues.py b/tests/test_pagure_flask_ui_issues.py
index 878cab6..ea8b874 100644
--- a/tests/test_pagure_flask_ui_issues.py
+++ b/tests/test_pagure_flask_ui_issues.py
@@ -1512,31 +1512,26 @@ class PagureFlaskIssuestests(tests.Modeltests):
 
             output = self.app.get('/test/tag/tag1/edit')
             self.assertEqual(output.status_code, 200)
-            self.assertTrue('<h2>Edit tag: tag1</h2>' in output.data)
-            self.assertTrue(
-                '<p>Enter in the field below the new name for the tag: '
-                '"tag1"</p>' in output.data)
+            self.assertTrue('<strong>Edit tag: tag1</strong>' in output.data)
 
             csrf_token = output.data.split(
                 'name="csrf_token" type="hidden" value="')[1].split('">')[0]
 
-            data = {'tag': 'tag2'}
+            data = {'tag': 'tag2',
+                    'tag_color': 'DeepSkyBlue'}
 
             output = self.app.post('/test/tag/tag1/edit', data=data)
             self.assertEqual(output.status_code, 200)
-            self.assertTrue('<h2>Edit tag: tag1</h2>' in output.data)
-            self.assertTrue(
-                '<p>Enter in the field below the new name for the tag: '
-                '"tag1"</p>' in output.data)
+            self.assertTrue('<strong>Edit tag: tag1</strong>' in output.data)
 
             data['csrf_token'] = csrf_token
             output = self.app.post(
                 '/test/tag/tag1/edit', data=data, follow_redirects=True)
             self.assertEqual(output.status_code, 200)
             self.assertIn(
-                '<title>Settings - test - Pagure</title>', output.data)
+                'Settings - test - Pagure', output.data)
             self.assertIn(
-                '</button>\n                      Edited tag: tag1 to tag2',
+                '</button>\n                      Edited tag: tag1(DeepSkyBlue) to tag2(DeepSkyBlue)',
                 output.data)
 
         # After edit, list tags
diff --git a/tests/test_pagure_lib.py b/tests/test_pagure_lib.py
index cdfd9c5..7677028 100644
--- a/tests/test_pagure_lib.py
+++ b/tests/test_pagure_lib.py
@@ -365,7 +365,6 @@ class PagureLibtests(tests.Modeltests):
         self.test_add_tag_obj()
         repo = pagure.lib.get_project(self.session, 'test')
         issue = pagure.lib.search_issues(self.session, repo, issueid=1)
-
         self.assertRaises(
             pagure.exceptions.PagureException,
             pagure.lib.remove_tags,
@@ -421,7 +420,9 @@ class PagureLibtests(tests.Modeltests):
             session=self.session,
             project=repo,
             old_tag='foo',
+            old_tag_color='DeepSkyBlue',
             new_tag='bar',
+            new_tag_color='black',
             user='pingou',
             ticketfolder=None,
         )
@@ -430,12 +431,14 @@ class PagureLibtests(tests.Modeltests):
             session=self.session,
             project=repo,
             old_tag='tag1',
+            old_tag_color='DeepSkyBlue',
             new_tag='tag2',
+            new_tag_color='black',
             user='pingou',
             ticketfolder=None,
         )
         self.session.commit()
-        self.assertEqual(msgs, ['Edited tag: tag1 to tag2'])
+        self.assertEqual(msgs, ['Edited tag: tag1(DeepSkyBlue) to tag2(black)'])
 
         # Add a new tag
         msg = pagure.lib.add_tag_obj(
@@ -448,29 +451,33 @@ class PagureLibtests(tests.Modeltests):
         self.assertEqual(msg, 'Tag added: tag3')
         self.assertEqual([tag.tag for tag in issue.tags], ['tag2', 'tag3'])
 
-        # Rename an existing tag into another existing one
-        msgs = pagure.lib.edit_issue_tags(
+        # Attempt to rename an existing tag into another existing one
+        self.assertRaises(
+            pagure.exceptions.PagureException,
+            pagure.lib.edit_issue_tags,
             session=self.session,
             project=repo,
             old_tag='tag2',
+            old_tag_color='black',
             new_tag='tag3',
+            new_tag_color='red',
             user='pingou',
             ticketfolder=None,
         )
-        self.session.commit()
-        self.assertEqual(msgs, ['Edited tag: tag2 to tag3'])
-        self.assertEqual([tag.tag for tag in issue.tags], ['tag3'])
 
-        self.assertRaises(
-            pagure.exceptions.PagureException,
-            pagure.lib.edit_issue_tags,
+        # Rename an existing tag
+        msgs = pagure.lib.edit_issue_tags(
             session=self.session,
             project=repo,
             old_tag='tag2',
-            new_tag='tag2',
+            old_tag_color='black',
+            new_tag='tag4',
+            new_tag_color='purple',
             user='pingou',
             ticketfolder=None,
         )
+        self.session.commit()
+        self.assertEqual(msgs, ['Edited tag: tag2(black) to tag4(purple)'])
 
     @patch('pagure.lib.git.update_git')
     @patch('pagure.lib.notify.send_email')
diff --git a/tests/test_pagure_lib_model.py b/tests/test_pagure_lib_model.py
index 7457430..9708b4a 100644
--- a/tests/test_pagure_lib_model.py
+++ b/tests/test_pagure_lib_model.py
@@ -132,17 +132,19 @@ class PagureLibModeltests(tests.Modeltests):
         issues = pagure.lib.search_issues(self.session, repo)
         self.assertEqual(len(issues), 1)
 
-        item = pagure.lib.model.Tag(tag='foo')
+        item = pagure.lib.model.Tag(tag='foo', tag_color='DeepSkyBlue',
+                                    project_id=repo.id)
         self.session.add(item)
         self.session.commit()
 
         item = pagure.lib.model.TagIssue(
+            issue=issues[0],
             issue_uid=issues[0].uid,
             tag='foo',
+            tag_id=item.tag_id
         )
         self.session.add(item)
         self.session.commit()
-
         self.assertEqual(str(item), 'TagIssue(issue:1, tag:foo)')